P12030 [USACO25OPEN] OohMoo Milk G 题解

dengchengyu · 2025-04-09 21:31:57 · 题解

显然当 m 越大时，使 m 加一或减一造成的变化量越大。

于是约翰的操作就是把最大 A 个加一，Nhoj 的操作就是把最大 B 个减一，然而直接动态维护这个过程是不好做的。

显然有一个结论，由于 B\le A，无论怎么操作最大的 A 个数还是那些数，于是排序后只考虑前 A 个数。那么约翰每次都会把这些数加一，于是考虑先把所有数加 D，然后接下来 Nhoj 可以做 D\times B 次操作，每次选择一个数使它减一，并且要满足一个数不能减超过 D 次，上述过程与原题意是等价的。

接下来我们二分一个数 mid，要使所有大于 mid 的数减到 mid 或是减完 D 次。如果还没完成这个过程次数就用完了，说明这个 mid 不合法，要找更大的 mid。否则如果还有剩余次数，那么亲自指定这些数最小减到 mid-1，然后统计答案并尝试寻找更小的 mid。

显然时间复杂度为 O(n\log V)。

const int N=1e5+5,mod=1e9+7;
int n,D,A,B,a[N];
signed main(){
    read(n,D,A,B);
    fo(i,1,n) read(a[i]);
    sort(a+1,a+1+n,greater<>());
    fo(i,1,A) a[i]+=D;
    int l=0,r=2e9,ans=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        int cnt=0;
        ll sum=0,res=0;
        fo(i,1,A) {
            if(a[i]>=mid) {
                int del=min(D,a[i]-mid);
                sum+=del;
                if(del<D) ++cnt;
                else res=(res+(ll)(a[i]-D)*(a[i]-D))%mod;
            }
            else res=(res+(ll)a[i]*a[i])%mod;
        }
        if(sum>(ll)D*B) {l=mid+1; continue;}
        fo(i,A+1,n) res=(res+(ll)a[i]*a[i])%mod;
        ll t=min((ll)cnt,(ll)D*B-sum);
        if(mid==0) t=0;
        res=(res+(ll)mid*mid%mod*(cnt-t))%mod;
        res=(res+(ll)(mid-1)*(mid-1)%mod*t)%mod;
        ans=res,r=mid-1;
    }
    write(ans);
    return 0;
}