专栏文章

P12030 [USACO25OPEN] OohMoo Milk G 题解

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipo2jjl
此快照首次捕获于
2025/12/03 15:09
3 个月前
此快照最后确认于
2025/12/03 15:09
3 个月前
查看原文
显然当 mm 越大时，使 mm 加一或减一造成的变化量越大。
于是约翰的操作就是把最大 AA 个加一，Nhoj 的操作就是把最大 BB 个减一，然而直接动态维护这个过程是不好做的。
显然有一个结论，由于 B≤AB\le A，无论怎么操作最大的 AA 个数还是那些数，于是排序后只考虑前 AA 个数。那么约翰每次都会把这些数加一，于是考虑先把所有数加 DD，然后接下来 Nhoj 可以做 D×BD\times B 次操作，每次选择一个数使它减一，并且要满足一个数不能减超过 DD 次，上述过程与原题意是等价的。
接下来我们二分一个数 midmid，要使所有大于 midmid 的数减到 midmid 或是减完 DD 次。如果还没完成这个过程次数就用完了，说明这个 midmid 不合法，要找更大的 midmid。否则如果还有剩余次数，那么亲自指定这些数最小减到 mid−1mid-1，然后统计答案并尝试寻找更小的 midmid。
显然时间复杂度为 O(nlog⁡V)O(n\log V)。
CPP
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;
}

评论

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

正在加载评论...