题解：P12030 [USACO25OPEN] OohMoo Milk G

hunengbuwuneng · 2025-09-10 15:44:03 · 题解

[USACO25OPEN] OohMoo Milk G

日志

2025.9.10 初稿

2025.12.19 被 HACK 修复

题意

两人玩游戏，初始有 n 个数，甲每天可以选 A 个数，使其所有值加 1，乙每天可以选 B 个数，使其所有值减 1，如此循环 m 天，甲希望最后序列平方和结果最大，乙反之，问最后序列平方和结果。

思路

如果你数感好的话，不难发现：

设 a、b 为非负整数，如果 a > b, 则 (a+1)^2-a^2 > (b+1)^2-b^2。

也就是说甲和乙的操作只能选最大的数，毕竟这样可以是自己增加值更多 / 对方增加值更少。

~~好这道题做完啦下班~~

这个时候蒟蒻看了一眼数据

m \leq 10^9

无法模拟啊……

所以此题最难点在于操作，贪心只是第一步。

首先可以发现，第 A+1 大的数和更后面的数是无法成为前 A 大的，因为操作只有又加又减和只加不减。那么我们直接把它们的平方和先求出来即可，后续不用管了。

那么现在每天的操作就是让每个数增加，再挑 B 个减回去。但是这样极难维护，因为每天的最值是会变化的。这里蒟蒻会先构造一组样例，共大家参考（以下图片以该数据为准进行操作）：

5 4
4 2
4 8 9 10 100

考虑先全部加上，再一个个清算：
先将所有值加 m 次，然后我们需要减 m\times B 次（注意每个数至多减 m 次，因为只有 m 天）。

然后我们尝试找一个标准值 x，每个值超过 x 时就一直减回去，保持在 x。

（此处 104 只能减去 m 的值，无法再减）

那什么样的标准值是合格的呢？只要以该值为标准值时减的次数比 m \times B 要多即可（多的部分后续调整），这样我们不难想到二分出最大合格标准值。（参照样例可确定该值为 11）
找出最大合格标准值，我们的序列也已经差不多了，但这里如果有多减的还需要调整。（这里的调整值最多为 A，不然还要更大的合格标准值 x+1 来抵消 A 的调整值。）
对于每一个值，如果他本身就比标准值大~~或相等~~（详见upd），则他一直在做又加又减，不可能调整给他（参照样例的 100）
如果他一直加都还比标准值小或相等，则他一直在做只加不减，无法调整让他继续加。
如果不满足上面两条，则说明该值做过又加又减和只加不减，最后值为 x(或 x+1 详见upd)，那么此时如果还有调整值，则可分配一点给他。（此处每个值至多被分配一点调整值，参照最开始的贪心思想）

做到这里已经结束了，算平方和即可。

upd:

我本来早就忘了这题，哪知被Hack了，特意修复了一下：

首先为啥会有值超过 x 呢？因为我们的被减的数可能是一堆 x，但是由于数量原因这些值有部分被放开限制，超过了 x，于是变为 x+1，这样的数不会少，但是不会集体变 x+1，那便可令 x 为 x+1。

这里沉重道歉，蒟蒻的疏忽可能导致的影响，也感谢Hack人员！

细节处理及实现

~~我写了半天还要写细节~~这题还有细节？各位直接看代码注释理解吧。

代码

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e5+7,M=1e9+7;
long long n,m,A,B,a[N],b[N],s,ans;
bool check(long long x){
    s=0;
    rep(i,1,A){
        if(a[i]+m<x) continue;//值太小减不了
        if(a[i]>=x) s+=m;//值太大一直减
        else s+=a[i]+m-x;
    }
    return s>=B*m;
}
signed main(){
    cin>>n>>m>>A>>B;
    rep(i,1,n){
        cin>>a[i];
    }
    sort(a+1,a+1+n,greater<int>());//降序排序操作
    long long l=0,r=a[1]+m;
    while(l<r){
        long long mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    check(l);
    s-=B*m;//此时s定义为调整值
    rep(i,1,A){
        if(a[i]>l) continue;//值太大加不了
        if(a[i]+m<=l){//值太小没法再多加
            a[i]+=m;
            continue;
        }
        a[i]=l;//唯一的细节就是如果没有调整值分配就只能是标准值
        if(s){
            s--;
            a[i]++;
        }
    }
    rep(i,1,n){
        ans=(ans+a[i]*a[i])%M;
    }
    cout<<ans;//愉快的输出~
    return 0;
}

结语

此题是一道思维好题，蒟蒻也花了不少功夫，各位可以自己画几个样例负责理解。

哦对了，还有公益广告：

（网格护眼，如有不适，请见谅，愿每位 OIer 都有一双健康的眼睛）