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