XTU 1246 Heartstone

$2016$长城信息杯中国大学生程序设计竞赛中南邀请赛$D$题

贪心。

我是这样贪的：开三个优先队列$q[0]$，$q[1]$，$q[2]$，$q[i]$存储对$3$取余之后为$i$的数。

首先看看还有没有$x\% 3 = 2$的$x$存在，如果有，那么这一次的$Arcane$ $Shot$就用在这个$x$上，更新答案与队列的情况。

如果$x\%3=2$的$x$不存在，那么看看$x\%3=1$的$x$是否存在，如果有，那么这一次的$Arcane$ $Shot$就用在这个$x$上，更新答案与队列的情况。

如果$x\%3=1$的$x$不存在，那么看看$x\%3=0$的$x$是否存在，如果有，那么这一次的$Arcane$ $Shot$就用在这个$x$上，更新答案与队列的情况。

具体看代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

const int maxn=;

int n,m,f[maxn],mod=1e9+;

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        priority_queue<int>q[]; memset(f,,sizeof f);

        for(int i=;i<=n;i++)

        {

            int x; scanf("%d",&x);

            q[x%].push(x); f[]=(f[]+x/)%mod;

            if(x%!=) f[]=(f[]+)%mod;

        }

        bool flag=;

        for(int i=;i<=m;i++)

        {

            if(!q[].empty())

            {

                int h=q[].top(); q[].pop();

                f[i]=f[i-]-; if(h->) q[].push(h-);

            }

            else if(!q[].empty())

            {

                int h=q[].top(); q[].pop();

                f[i]=f[i-]-; if(h->) q[].push(h-);

            }

            else if(!q[].empty())

            {

                if(flag==) f[i]=f[i-], flag=;

                else

                {

                    int h=q[].top(); q[].pop();

                    f[i]=f[i-]-; if(h->)  q[].push(h-);

                    flag=;

                }

            }

            else f[i]=f[i-];

        }

        int ans=;

        for(int i=;i<=m;i++) ans=(ans+f[i])%mod;

        cout<<ans<<endl;

    }

    return ;

}