ABC 313 G 题解

Purslane · 2023-08-09 19:50:21 · 题解

Solution

简单题。我们不妨把每个位置看做一座小山，石子的数量是小山的高度。

那么每次只有两种操作：把所有山的山头削低一格；把所有山的山头升高一格。注意不能是负数。

我们发现，操作一有点类似“拉平效应”，如果两座山头都比较矮，那么经过几次操作一之后他们高度都变成了零，之后也就一直一样了。

因此我们会设一个阈值 W，所有 a_i \le W 都会变成 W，然后再整体往下减。

我们应当指出，只要往下减之后所有山高度的总数小于等于原来的高度，那么一定有解。因为你可以执行 W 次操作 1，再往回加就一定是合法的构造。

我们枚举填平层的上面那一层，这一层及上方的总数为 pre_h，那么答案为 \lfloor \frac{tot-pre_h}{n} \rfloor +1。

然后你发现 h 增加时 pre_h 是等差数列，于是就可以使用类欧几里得算法模板在 O(\log V) 的复杂度内计算每一段的贡献。所以总的复杂度是 O(n \log V)。

代码：

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,MOD=998244353; 
int n,tot,h[MAXN],ans;
map<int,int> mp;
int f(int a,int b,int c,int n) {
    if(n<=0) return 0;
    int A=(a%c+c)%c,B=(b%c+c)%c;
    if(A!=a||B!=b) {
        int aa=(a-A)/c%MOD,bb=(b-B)/c%MOD,ans0=(bb*n%MOD+n*(n+1)/2%MOD*aa)%MOD;
        return (ans0+f(A,B,c,n))%MOD;
    }
    if(a==0) return (b/c)%MOD*n%MOD;
    int m=(a*n+b)/c,ans0=m%MOD*n%MOD;
    return ((ans0-f(c,-b-1,a,m))%MOD+MOD)%MOD;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n; ffor(i,1,n) cin>>h[i],mp[h[i]]++,tot+=h[i];
    mp[0]++; int pre=0,cnt=0;
    for(auto it=--mp.end();it!=mp.begin();it--) {
        auto It=it; It--;
        cnt+=it->second;
        if(cnt==n) break;
//      cout<<-cnt<<' '<<tot-pre<<' '<<n<<' '<<it->first-It->first<<' '<<f(-cnt,tot-pre,n,it->first-It->first)<<'\n';
        ans=(ans+it->first-It->first+f(-cnt,tot-pre,n,it->first-It->first))%MOD;
        pre=pre+(it->first-It->first)*cnt;
    }
    ans+=tot/n+1;
    ans=(ans%MOD+MOD)%MOD;
    cout<<ans;
    return 0;
}