Gym - 101775J Straight Master——差分

Gym - 101775J Straight Master——差分

题意：给你一个序列，每次可以随便选一个大小为3~5的区间，将区间内的数减1，问最后能不能把整个序列变为0

思路：构造差分序列b【i】=a【i】-a【i-1】，比如1 3 2 5 1的差分序列就是1 2 -1 3 -4，这样将区间【l，r】内的所有数减一相当于把b【l】减一， 把b【r+1】加一，基于这个思想我们从左到右扫整个序列，遇到正数就找他右面离他最近的负数，把这个负数尽量变为0，变为0后若正数还有剩余，就继续往右找负数直到这个正数用完，当然找到负数以后要判断一下负数与正数之间的距离是否小于三，小于三肯定不满足题意了，直接输出no就好了，这样扫完整个序列后差分数组的每个数应该都是0，都是0的话输出yes，否则no

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 2e5 + 10;int T, n, a[maxn], b[maxn];bool solve() { int p = 4; for (int i = 1; i <= n+1; i++) { while (b[i] > 0) { while (p <= n+1 && b[p] >= 0) p++; if (p > n+1 || p - i < 3) return false; if (b[p] + b[i] >= 0) { b[i] += b[p]; b[p] = 0; } else { b[p] += b[i]; b[i] = 0; } } if (b[i] != 0) return false; } return true;}int main() { //freopen("out.txt", "w", stdout); scanf("%d", &T); for (int ks = 1; ks <= T; ks++) { scanf("%d", &n); a[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i] - a[i-1]; } b[n+1] = 0 - a[n]; printf("Case #%d: ", ks); if (solve()) puts("Yes"); else puts("No"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。