题解：P11393 [JOI Open 2019] 送金

· · 题解

upd on 2024.12.20：修正了次数上界的错误，修改了代码中的错误，感谢 rizynvu 的指正。

双倍经验：CF2038B。

观察到当 A_i>B_i 时，我们必须通过汇款使得 A_i\leq B_i 才可能有解，不妨先做尽可能多的操作使得 A_i\leq B_i。特别的，当 B_i=0 时，因为你不能让 A_i 变成负的，所以降到 A_i=1 就暂时不能再降了。

我们从 i=1 开始，执行这个汇款操作足够多次，直到不能操作为止，然后判断是否有所有的 A_i=B_i 成立。这样看上去特别对，但是不太好证。一个感性的理解就是，如果有解，相邻两个位置之间汇款的次数是唯一确定的，而这样操作保证了每个位置不会超过次数的上界，因此不会提前把自己卡死，同时肯定在所有位置都达到上界之前一定存在一个位置可以继续调整，也就一定能调整出解。

然后我们考虑需要调整多少轮。考虑我们执行一圈以后，几乎所有多余的数都被推到了一个位置上，对于其他位置，若 B_i=0，有 A_i=0 或 A_i=1；否则 B_i\neq 0，有 A_i-B_i=0 或 A_i-B_i=-1。考虑这个位置的 A_i-B_i，设为 V，且 V 是所有 A_i-B_i 的最大值。当 V>2 时，每在 V 处做一次操作，V 都会减小，变成一个不超过 \lfloor\frac{V}{2}\rfloor+1 的值，因此做 O(\log V) 轮后我们能得到 V\leq 2。此时有一种特殊的情况，即当前 V=2，下一个位置刚好满足 B_i=0,A_i=1，这个时候做一次操作 V 不变。但是不可能一直出现这样的情况，至多再转一圈就会停下来。综上，我们只需要执行一圈，多做 O(\log V) 次，再执行一圈，就一定能调整完。

注意，由于 N 可能小于 \log V，在设置循环次数时应当设为 kN+d，其中 k,d 是足够大的常数，其下界在上文已经做过分析。时间复杂度 O(N+\log V)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[1000005],b[1000005];
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i] = x - y;
        if(!y)
            b[i] = 1;
    }
    for(int i = 0;i < n * 2 + 50;i++)
    {
        int p = i % n,q = (i + 1) % n;
        if(a[p] < 0)
            continue;
        int tmp = (a[p] + 1) / 2;
        if(b[p])
            tmp = a[p] / 2;
        a[q] += tmp,a[p] -= tmp * 2;
    }
    for(int i = 0;i < n;i++)
        if(a[i] != 0)
        {
            printf("No\n");
            return 0;
        }
    printf("Yes\n");
    return 0;
}