P17174 「MSOI R1」距离 题解
也挺水的一道题 但是感觉比较好玩
题目见P17174 「MSOI R1」距离 - 洛谷
发现给定的单纯的d不太好处理，我们可以用前缀和思想来将d转化为这个人的实际位置（即坐标）
特别地，第一个人位置是0
我们发现，基本需要对所有是1的同学进行操作。那怎么搞呢
因为t[i] = 0的同学动不了。且第一个和最后一个同学都动不了，即t[1] = t[n] = 0。那任意一个要动的人必定夹在两个动不了的人的中间。
又根据题目中且要求他最终与左右邻居的距离相等，我们可以对于任何一个要动的人，令其左边最近一个动不了的人坐标是\(L\)，右边最近一个动不了的人坐标是\(R\)
那么我们发现，\(L\)和\(R\)中间包着的要动的人，其距离总有\(d[i] - d[i-1] = d[i+1] - d[i]\)
那不就是个等差数列！
公差也就呼之欲出了：\(\frac{d[R]-d[L]}{R-L+1}\)
那么，对于一个要动的人，他理想的情况下应该在：\(d[i] = L + i \times \frac{d[R]-d[L]}{R-L+1}\)
为了避免分式计算的不必要的麻烦，我们消去右式的分母
则有：\(d[i] = L + i \times \frac{d[R]-d[L]}{R-L+1}\)
\(\Rightarrow\) \((d[i]-L) \times (R-L+1) = i \times (d[R]-d[L])\)
那我们接下来的操作就很显而易见了：先找两个不能动的 对他们中间的人处理理想的的位置 然后如果这个人不在他理想的位置 ans++
代码如下:
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
inline int read(){int x = 0; bool f = 1; char c = getchar();for(; !isdigit(c); c = getchar()) if(c == '-') f = 0;for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return f ? x : -x;
}
const int N = 2e5 + 10;
int n, d[N], flag[N];
main(){// freopen(".in", "r", stdin), freopen(".out", "w", stdout);n = read();int ans = 0;for(int i = 2, aa; i <= n; ++i){aa = read();d[i] = aa + d[i - 1];}for(int i = 1; i <= n; ++i){flag[i] = read();}int fix[N], cnt = 0;for(int i = 1; i <= n; ++i){if(!flag[i]) fix[++cnt] = i;//统计不能动的，记录编号}for(int i = 1; i <= n; ++i){if(flag[i]){int l = 1, r = cnt, pos = -1;while(l <= r){int mid = (l + r) >> 1;if(fix[mid] >= i){pos = mid;r = mid - 1;}else{l = mid + 1;}}//二分查找区间int L = fix[pos - 1], R = fix[pos];if((d[i] - d[L]) * (R - L) != (d[R] - d[L]) * (i - L)){ans++;}}}cout << ans << endl;return 0;
}
递交记录