题解：CF2038B Make It Equal

· · 题解

题目链接

CF2038B Make It Equal

题意简述

这东西好久没写了啊。

阿瓦在一个幻想王国里。

他走在草坪上，发现有 1 \le n \le 2 \times 10^5 个数字精灵祝他生日快乐。

阿瓦非常开心。因为最多可能会有 2 \times 10^5 个精灵为他庆生。

但是，对于每个数字精灵都有一个饱食度 1 \le a_i \le 10^9，如果有任意两个数字精灵的饱食度不同，那么他们就会不开心。

不过此时，机智的阿瓦想到了一个策略：那就是跟数字精灵们玩一个游戏。顺便趁这个时候改变数字精灵的饱食度状况。

这个游戏的实质内容就是将这 n 个数字精灵围成一个圈，你可以进行对相邻的两个数字精灵更改饱食度的一次操作，具体的，将左边的数字精灵的饱食度 -2，将右边的数字精灵的饱食度 +1。

你需要求出最少的操作次数。

解题思路

发现这东西是可以二分答案的。

为啥呢？

你发现你将所有的人做一次操作，就是全局减一。

那么你可以将所有的 a_i 尽量减少到最小的 a_i，这么做操作，你感性理解，发现这种操作的数量一定不多，为啥呢？你发现一次整体操作之后，那么它们所有数字的值可能都只会推到一个数字上，其余数字的差将会不超过 1，那么你会发现，后面几次操作都在调整最后一个数字，而你最后一个数字是持续推动的，所以操作次数一定小于 \log n 次，直接暴力做就行了。

参考代码

#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define cll const ll
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
ll _t_;
void _clear(){}
ll n;
ll a[1000010];
ll L,R;
ll b[1000010];
ll nxt(ll x)
{
    if(x==n)
        return 1;
    return x+1;
}
ll check(ll Mid)
{
    ll sum=0;
    forl(i,1,n)
        b[i]=a[i];
    forl(_,1,40)
        forl(i,1,n)
            if(b[i]>Mid)
            {
                ll need=(b[i]-Mid+1)/2;
                sum+=need;
                b[i]-=need*2;
                b[nxt(i)]+=need;
            }
    forl(i,1,n)
        if(b[1]!=b[i] || b[i]<0)
            return 1e18;
    return sum;
}
void solve()
{
    _clear();
    cin>>n;
    forl(i,1,n)
        cin>>a[i];
    L=0,R=2e9;
    while(L<R)
    {
        ll Mid=(L+R+1)/2;
        if(check(Mid)!=1e18)
            L=Mid;
        else
            R=Mid-1;
    }
    if(check(L)!=1e18)
        cout<<check(L)<<endl;
    else
        cout<<-1<<endl;
}
int main()
{
//    freopen("tst.txt","r",stdin);
//    freopen("sans.txt","w",stdout);
    IOS;
    _t_=1;
    cin>>_t_;
    while(_t_--)
        solve();
    QwQ;
}