P9815 题解

xz001 · 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;
}