题解：P9815 wbyblD

LAI_Jalen · 2026-11-10 21:20:33 · 题解

为了方便，题解中设当前点为 x。

题解背景

发现自己玩 OI 快两年了还没有在你谷发过一篇题解，于是随便找了一道题做了一下来水一篇题解 qwq

题目大意

本题其实可以当作反弹来理解。

小球从最左侧 0 号点出发，用 x 表示当前位置，如果当前运动方向向右（y=1）且 a_x > 0，方向反弹成向左运动；如果当前运动方向向左（y=-1）且 b_x > 0，方向反弹成向右运动。

题目解析

很容易发现，我们对每个点都进行枚举是一定会超时的。我们可以对当前点的反弹次数进行考虑。

我们维护一个变量（代码中为 bal）来存储当前点左侧的所有点 b 的总和为多少。这可以用于判断我们是否可以通过当前点：对于当前点的 a_x > bal，容易发现把左侧所有 b 都消耗完之后，还是无法反弹通过当前点，最终一定会向左运动到 0 号点。答案为 0。

若当前点的 a_x \leq bal，则能够通过反弹通过当前点，消耗的反弹次数为 a_x，新的 bal = bal - a_x。

由于 bal 的值表示左侧所有点 b 的总和，我们需要从左往右遍历每个点，并对当前点进行上述的判断之后，把每个点的 b_x 加到 bal 中。容易发现，只要能够遍历到 n+1 号点，说明任何点都可以被通过，答案为 n+1。

时间复杂度 O(n)。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,a,b,bal,ans,flag;
signed main(){
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        bal=0;
        ans=n+1;
        flag=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%lld %lld",&a,&b);
            if(flag==0)
            {
                if(bal<a)
                {
                    ans=0;
                    flag=1;
                }
                else
                {
                    bal=bal-a+b;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}