学习总结二十九

发布于:2025-02-11 ⋅ 阅读:(65) ⋅ 点赞:(0)

公路维修问题

这里首先先明白题意,就是一段路分为m段,只需要分m-1次。我们先要解决的的问题是如何在合适的地方截断。案例给出,发现第一段的末与第二段的头的位置相差很大,而每一段的每个坑位相差不是很大 。,所以就知道如何截断。

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	int a[15005], b[15005];//a数组用来存坑的坐标,b数组用来记录相邻坑位的距离
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int sum = 0;
	for (int i = 1; i < n; i++)
	{
		b[i - 1] = a[i] - a[i - 1];
	}
	sort(b, b + n);//对b数组进行升序排序
	for (int i = 0; i < n - m + 1; i++)
	{
		sum += b[i];
	}
	cout << sum + m;
	return 0;
}

第三个循环的意思是i<n-(m-1),以题目给出的代码为例,18个坑,算出每个坑的差值(没有管制的路段)并升序排序,去掉后面差值最大的三个(8-14,21-25,31-40),sum的值就代表不进行管制的路段的和。

最后输出sum+m。因为每一段距离等于两个坐标点相减再加一(但路不是坐标点,可以看成长度为一的线段,自己画图就理解了),有m段,再加m。 

faebdc玩扑克

感觉挺简单,但实现拿不到满分。第一次的代码(60):

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int a[100005];
	int k=0;
	for (int i = n; i > 0; i--)
	{
		a[k++] = i;//倒序放入数组
		int temp = a[0];
		for (int j = 0; j < k - 1; j++)
		{
			a[j] = a[j + 1];//数组依次向前移位
		}
		a[k - 1] = temp;//将第一个放到数组末尾,模拟。
	}
	for (int i = n-1; i >=0; i--)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

仔细观察发现:用1,2,3来举例,如果想要输出1,2,3,反推可得原来的序列为2,1,3。多举几个就会发现1永远会在第二号位。 

看题解就更加简洁了,大佬原话:从最后的状态向前推,发现每次操作就是向开头插入当前未在数组中的最大值,然后把数组尾元素插到数组头部。

拙劣模仿:

#include<iostream>
#include<queue>
using namespace std;
queue<int>a;
int s[1005], ans[1005];
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		a.push(i);
	}
	for (int i = 1; !a.empty(); i++)//模拟过程
	{
		a.push(a.front());
		a.pop();
		s[i] = a.front();
		a.pop();
	}
	for (int i = 1; i <= n; i++) {
		ans[s[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
	return 0;
}

以13为例,经过模拟:3,6,1,7,4,10,5,11,2,12,8,13,9。

举个例子,例如s[1]=3,那么ans[3]=1。大佬的虽然nb,但是难懂。我自己的又不行。。。