题目内容就直接跳过了,大家自行看题。
主要讲讲这道题目的思路:
这道题我们其实就是先排个序,然后每次我们枚举一下每个点的情况即可。
具体分析
首先我们的第一个点一定是往右移动的因为往右移动的决定怎么样都不会比往左移动差
(差指的是把左右边界差变得更大了)
同理我们的最后一个点一定是往左移动的因为往左移动的决定怎么样都不会比往右移动差
解决完这两个点以后我们就可以继续往后枚举每个点的移动情况:
首先我们要明白一个性质:
比如说假设当前点为 i , 然后我让 i 往右移动,i 点就有可能拓宽我们的右边界(右边界指的是比最后一个点往左移动x格的坐标还有靠右)。如果我们一旦决定了 i 往右移动,那么我们 i 左边的点都可以尽管放心往右移动,原因很简单:
1.往右移动一定不会拓宽左边的边界
2.往右移动就算移动到比最后一个点往左移动x格的坐标还有靠右的点也没所谓,因为第i个点一定走得比它更远
(i + x > (i - t) + x, i - t >= 1)
然后往左移动也是同理。
所以:
一旦确定确定某个点往左移那么其右边的点都能往左移
一旦确定确定某个点往右移那么其左边的点都能往右移
因此我们只要枚举分割点,让分割点左边的点往右移动,分割点右边的点往左移动
然后比较找到左边界和右边界之差最小的方案即可
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100; int n; int p[N], x; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &p[i]); scanf("%d", &x); sort(p + 1, p + n + 1); int ans = (p[n] - p[1]); for(int i = 1; i < n; i++) { ans = min(ans, (max(p[n] - x,p[i] + x) - min(p[1] + x,p[i + 1] - x))); } printf("%d\n", ans); }