题意:
题意简单明了,就不多赘述了。
解题方法:
这道题我们要考虑贪心。由于我们只有一次修改 \(a_i\) 的机会,所以我们修改的值一定是产生最小距离的两个相邻的点之中修改。
那么如何修改是最优的呢?有一下两种情况:
-
插入到距离最大的两个相邻点的最中间。因为只有插入到距离最大的两个相邻点的最中间,才能使它和相邻的点的距离最大。
-
插入到最后的 \(d\) 这个时间。
在这两种情况中取最近距离的 \(max\) 即可。
另外注意,这里求距离的公式有点另类。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int t, n, d, a[200001];
int dis(int x, int y) {return a[x] - a[y] - 1;}
int f(int x)
{
int Min = 2e9, Max = 0, last = 0; //Min表示最小值,Max表示最大值,last表示当前为止的最后一个点
for (int i = 1; i <= n; i ++)
{
if (i == x) continue; //千万注意要continue
Min = min(dis(i, last), Min);
Max = max(dis(i, last), Max);
last = i;
}
return min(Min, max((Max - 1) >> 1, d - a[last] - 1));
}
int main()
{
scanf("%d", &t);
while (t --)
{
int minn = 2e9, minx, ans = 0;
scanf("%d%d", &n, &d);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
if (dis(i, i - 1) < minn) //读入的时候顺便取min
{
minn = dis(i, i - 1);
minx = i;
}
}
ans = f(minx);
if (minx != 1) ans = max(ans, f(minx - 1)); //如果minx为1,就不能修改它前面的点了(以为它前面没有点)
printf("%d\n", ans);
}
}
标签:last,Exam,修改,int,题解,距离,相邻,Rescheduling,题意
From: https://www.cnblogs.com/tongyuxin/p/17120307.html