专栏文章

题解：P12030 [USACO25OPEN] OohMoo Milk G

hhunengbuwuneng
P12030题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miny7lh7
此快照首次捕获于
2025/12/02 10:17
3 个月前
此快照最后确认于
2025/12/02 10:17
3 个月前
查看原文

[USACO25OPEN] OohMoo Milk G

日志

2025.9.10 初稿

题意

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

思路

如果你数感好的话，不难发现：
设 aa、bb 为非负整数，如果 a>ba > b, 则 (a+1)2−a2>(b+1)2−b2(a+1)^2-a^2 > (b+1)^2-b^2。
也就是说甲和乙的操作只能选最大的数，毕竟这样可以是自己增加值更多 / 对方增加值更少。
好这道题做完啦下班
这个时候蒟蒻看了一眼数据
m≤109m \leq 10^9
无法模拟啊……
所以此题最难点在于操作，贪心只是第一步。
首先可以发现，第 A+1A+1 大的数和更后面的数是无法成为前 AA 大的，因为操作只有又加又减和只加不减。那么我们直接把它们的平方和先求出来即可，后续不用管了。
那么现在每天的操作就是让每个数增加，再挑 BB 个减回去。但是这样极难维护，因为每天的最值是会变化的。 这里蒟蒻会先构造一组样例，共大家参考（以下图片以该数据为准进行操作）：
CPP
5 4
4 2
4 8 9 10 100
  • 考虑先全部加上，再一个个清算：
  • 先将所有值加 mm 次，然后我们需要减 m×Bm\times B 次（注意每个数至多减 mm 次，因为只有 mm 天）。
1-1
  • 然后我们尝试找一个标准值 xx，每个值超过 xx 时就一直减回去，保持在 xx。
2-1
（此处 104104 只能减去 mm 的值，无法再减）
  • 那什么样的标准值是合格的呢？只要以该值为标准值时减的次数比 m×Bm \times B 要多即可（多的部分后续调整），这样我们不难想到二分出最大合格标准值。（参照样例可确定该值为 1111）
  • 找出最大合格标准值，我们的序列也已经差不多了，但这里如果有多减的还需要调整。（这里的调整值最多为 AA，不然还要更大的合格标准值 x+1x+1 来抵消 AA 的调整值。）
  • 对于每一个值，如果他本身就比标准值大或相等，则他一直在做又加又减，不可能调整给他（参照样例的 100100）
  • 如果他一直加都还比标准值小或相等，则他一直在做只加不减，无法调整让他继续加。
  • 如果不满足上面两条，则说明该值做过又加又减和只加不减，最后值为 xx，那么此时如果还有调整值，则可分配一点给他。（此处每个值至多被分配一点调整值，参照最开始的贪心思想）
3-1做到这里已经结束了，算平方和即可。

细节处理及实现

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

代码

CPP
#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 都有一双健康的眼睛）

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...