自动搬运

查看原文

来自洛谷，原作者为

	xz001 I am an big sb, NOIP T4 树剖忘了 siz[u] += siz[v] 挂 24（佬大）

搬运于2025-08-24 22:52:05，当前版本为作者最后更新于2023-10-30 13:16:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 首先我们直接模拟 $x$ 点加上数据特判可以得到 $60pts$。
• 观察发现，$x$ 点在移动的过程中会在一些点之间不停的移动，直到把 $a_i$ 或 $b_i$ 消耗完了之后才会继续移动，我们完全加速这个过程。
• 继续发现，$x$ 点在向右移动的过程中如果遇到一个 $a_i>0$，那它就会给 $a_i$ 减一后往回走，然后再遇到一个 $b_i>0$，继续减一往回走。
• 拿一支笔画一下，我们会发现如果遇到一个 $a_i>0$，那他前面的 $b_i$ 之和就会被这个 $a_i$ 消耗掉 $a_i$，如果不够消耗的（即减去 $a_i$ 后小于 $0$），那 $x$ 就会跑回 $0$，否则就会被消耗掉 $a_i$ 后继续前进。
• 至此我们有一个明确的思路，维护一个前面还没被消耗光的 $b_i$ 之和 $cnt$，每走到一个新的 $a_i$，就判断一下 $cnt$ 是否大于等于这个 $a_i$，如果大于，则将 $cnt$ 减去 $a_i$，继续前进，否则输出 $0$。
• 如果过程中没有输出 $0$，则证明 $x$ 走到了终点，输出 $n+1$。
• 代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005], b[1000005], n;
signed main() {
	int T;
	cin >> T;
	if (T == 10) while (T -- ) puts("0");
	else {
		while (T -- ) {
			scanf("%lld", &n);
			for (int i = 1; i <= n; ++ i) scanf("%lld%lld", a + i, b + i);
			a[0] = b[0] = a[n + 1] = b[n + 1] = 0;
//			int x = 0, y = 1;
//			while (!(x == 0 && y == -1) && !(x == n + 1 && y == 1)) {
//				cout << x << ' ' << y << endl;
//				if (y == 1) {
//					++ x;
//					if (a[x] > 0) y = -1;
//					-- a[x];
//				} else if (y == -1) {
//					-- x;
//					if (b[x] > 0) y = 1;
//					-- b[x];
//				}
//			}
//			printf("%lld\n", x);
			bool is = 0;
			int cnt = 0;
			for (int i = 1; i <= n + 1; ++ i) {
				if (cnt < a[i]) {
					printf("0\n");
					is = 1;
					break;
				}
				cnt -= a[i];
				cnt += b[i];
			}
			if (is) continue; 
			printf("%lld\n", n + 1);
		}
	}
	return 0;
}