题解 P6831 - [IOI2020] 嘉年华奖券

小清新 IOI 题。

首先考虑怎么求出答案。等价于我选择 \(\dfrac{nk}{2}\) 个数令它们系数为 \(1\)，再选 \(\dfrac{nk}{2}\) 个数令它们系数为 \(-1\)，最大化每个数的值乘以系数之和，并且要求每个奖券选择的数的个数恰好是 \(k\) 个。

考虑先令每个奖券的前 \(k\) 个数系数为 \(-1\)，然后再将 \(\dfrac{nk}{2}\) 个数改成正数。因为每次我显然是选择一个奖券，将最靠右的负数去掉，再选择最靠左的没有选择的数作为正数，而你发现这个贡献是凸的，所以优先队列维护即可。时间复杂度 \(O(nm\log n)\)。

最后考虑怎么构造方案。直接每次选择剩余负数最多的 \(\dfrac{n}{2}\) 个奖券填上 \(-1\)，另外 \(\dfrac{n}{2}\) 个奖券填上 \(+1\) 即可。你可能会担心如果这 \(n\) 个奖券的 \(\pm 1\) 的系数不符合我们构造出来的系数怎么办，不过仔细想想不会出现这样的情况。因为我们选择的最大的负数肯定不会超过最小的正数，否则我们一定可以交换这两个数的系数使得答案变得更优，于是 \(\pm 1\) 的系数一定是对的，直接 xjb 取即可。

const int MAXN=1500;
int n,m,pt[MAXN+5],coef[MAXN+5][MAXN+5],L[MAXN+5],R[MAXN+5];
ll find_maximum(int k,vector<vector<int> >x){
	n=x.size();m=x[0].size();int cnt=n*k/2;
	for(int i=0;i<n;i++)for(int j=0;j<k;j++)coef[i][j]=-1;
	for(int i=0;i<n;i++)pt[i]=k-1;
	priority_queue<pii>q;
	for(int i=0;i<n;i++)q.push(mp(x[i][m-1]+x[i][k-1],i));
	while(cnt--){
		pii p=q.top();q.pop();int id=p.se;
		coef[id][pt[id]]=0;coef[id][pt[id]+m-k]=1;--pt[id];
		if(pt[id]>=0)q.push(mp(x[id][pt[id]+m-k]+x[id][pt[id]],id));
	}
	ll res=0;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)res+=coef[i][j]*x[i][j];
	vector<vector<int> >ans;ans.resize(n);
	for(int i=0;i<n;i++)ans[i].resize(m);
	for(int i=0;i<n;i++)L[i]=pt[i],R[i]=pt[i]+m-k+1;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)ans[i][j]=-1;
	for(int i=0;i<k;i++){
		static int ord[MAXN+5];
		for(int j=0;j<n;j++)ord[j]=j;
		sort(ord,ord+n,[&](int x,int y){return L[x]>L[y];});
		for(int j=0;j<n/2;j++)ans[ord[j]][L[ord[j]]]=i,--L[ord[j]];
		for(int j=n/2;j<n;j++)ans[ord[j]][R[ord[j]]]=i,++R[ord[j]];
	}
	allocate_tickets(ans);
	return res;
}