学习总结二十九

公路维修问题

这里首先先明白题意，就是一段路分为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，但是难懂。我自己的又不行。。。