自动搬运

查看原文

来自洛谷，原作者为

	小杨小小杨 如果来生太远寄不到诺言 不如学着放下许多执念 以这断句残篇向岁月吊唁 老去的当年 水色天边 有谁将悲欢收殓|去掉.cn看主页

搬运于2025-08-24 22:19:26，当前版本为作者最后更新于2023-10-16 16:27:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

背景

被教练拉去做的题目....想到一个题解们似乎都没想到的离谱做法然后代码有一说一自己都不是很理解反正下意识打的然后莫名其妙就过了。

思路

要求自身价值最大，那么显而易见，Alice 和 Bob 会选取当前序列中最大的那个数字。
然后怎么处理呢？
首先考虑优先队列，每次把队头弹出，压入下一个数字。时间复杂度过大会 TLE。
分析得到，我们可以发现，在第 $i$ 回合中，取得人肯定是取越大越好，这样就有一个莫名其妙的单调性。
考虑对原数组排序，按照第一关键字是数值从大到小，第二关键字是位置从小到大进行排序，然后每一次询问必然会做 $n$ 次，那么久扫一遍排序后的数组，贪心策略在当前的回合下，第一个遇到的数字必然就是最优情况。
说的通俗一点就是提前先占坑占好，然后下一次模拟到这个位置时直接跳过他的回合。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,i,fl[100010],greed,j,x,sum,b[100010];
long long Alice,Bob;
struct Node{int sum,i;}a[100010];
bool cmp(Node x,Node y){return x.sum>y.sum||x.sum==y.sum&&x.i<y.i;}//双关键字排序
void work(int x,int s){if (x&1) Alice+=s;else Bob+=s;}//当前回合取的人
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) scanf("%d",&a[i].sum),a[i].i=i;
	sort(a+1,a+n+1,cmp);//预处理排序
	for (i=1;i<=m;i++){
		Alice=Bob=0;scanf("%d",&x);sum=0;greed=0;
		for (j=1;j<=n;j++) b[j]=0; 
		for (j=1;j<=n;j++)
			if (a[j].i<=greed+x-1){greed++;while (b[greed]) greed++; work(greed,a[j].sum);}//如果当前是一开始就有的数组，那么就处理它
			else work(a[j].i-x+1,a[j].sum),b[a[j].i-x+1]=1;//不然提前占坑
		printf("%lld\n",Alice-Bob);
	}
	return 0;
}