问题 B: Game

时间限制: 1 Sec  内存限制: 256 MB

题面

---

题面谢绝公开。

题解

---

对于最初加入的每一个元素开桶记录出现次数。

然后记录一个前p个元素最大值。

先由先手玩家取走一个最大值并判定最大值是否改变。

然后就可以先向集合中加入一个元素再由本轮取数的玩家取走最大的数字。

如果加入的元素大于最大值，由本轮取数的玩家直接取走。否则累加该数$sum$，取走一个最大值。

这样可以保证指针单调不升，减少指针移动次数。离散化可以进一步减少指针移动次数。

（然而我常数写丑了并不能A掉。多谢评测机放过在下。原封不动的代码多交几遍就A了）

 

#include<bits/stdc++.h>
#define rint register int
using namespace std;
inline void read(int &A)
{
    A=0;int B=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')B=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){A=(A<<3)+(A<<1)+ch-'0';ch=getchar();}
    A=A*B;
}
int n,k,a[100005],sum[100005],mx,lsh[100005];
long long ans1,ans2;
int main()
{
    read(n),read(k);
    for(rint i=1;i<=n;++i)read(a[i]),lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    rint cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    for(rint i=1;i<=n;++i)
        a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
    for(rint Round=1,pi;Round<=k;++Round)
    {
        read(pi);ans1=ans2=0;
        for(rint i=1;i<=pi;++i)
            ++sum[a[i]],mx=max(mx,a[i]);
        ans1+=lsh[mx];--sum[mx];
        while(!sum[mx]&&mx>0)--mx;
        for(rint i=2;i<=n;++i)
        {
            if(i&1)
            {
                if(pi<n)
                {
                    ++pi;
                    if(a[pi]>mx)ans1+=lsh[a[pi]];
                    else ans1+=lsh[mx],--sum[mx],++sum[a[pi]];
                }
                else ans1+=lsh[mx],--sum[mx];
            }
            else
            {
                if(pi<n)
                {
                    ++pi;
                    if(a[pi]>mx)ans2+=lsh[a[pi]];
                    else ans2+=lsh[mx],--sum[mx],++sum[a[pi]];
                }
                else ans2+=lsh[mx],--sum[mx];
            }
            if(i==n)break;
            while(!sum[mx]&&mx>0)--mx;
        }
        printf("%lld\n",ans1-ans2);
    }
    return 0;
}

View Code