P6294 [eJOI2017] 魔法 解题报告

· · 题解

背景

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

思路

要求自身价值最大，那么显而易见，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;
}