[贪心][优先队列] UVa 1623 Enter the Dragon

从后往前，如果遇到下雨的天气就存进优先队列里，如果遇到不下雨的天气，优先解决离当前位置最近的湖，用vis记录一个湖是否有危险，如果遇到一个下雨天这个湖已经有危险了那么就输出NO，否则标记为有危险，如果是不下雨的天有则把有危险的（队列中的）前一个最大的湖去掉。到最后如果队列非空则也输出NO，说明有的湖的危险没有解决。

#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;

typedef struct node
{
    int x,nl;
    node(){}
    node(int x,int nl):x(x),nl(nl){}
    bool operator< (const struct node &rhs)const {return nl S;

int main()
{
    int T,n,m;
    scanf("%d",&T);

    while(T--)
    {
        while(!S.empty())S.pop();
        memset(last,0,sizeof(last));
        memset(vis,0,sizeof(vis));
        cnt=0;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++)
        {
            scanf("%d",&a[i]);
            ori[i].x=a[i];
            ori[i].nl=last[a[i]];
            last[a[i]]=i;
            cnt+=(a[i]==0);
        }
        if(a[1]||(cnt<<1)0;i--)
        {
            if(a[i])
            {
                if(!vis[ori[i].x])
                {
                    S.push(ori[i]);
                    vis[ori[i].x]++;
                }
                else
                {
                    while(S.empty())S.pop();
                    flag=1;
                    printf("NO\n");
                    break;
                }
            }

            if(!S.empty()&&!a[i])
            {
                ans[i]=S.top().x;
                S.pop();
                vis[ans[i]]--;
            }
            else
            {
                ans[i]=0;
            }
        }
        if(flag)
            continue;
        if(!S.empty())
        {
            printf("NO\n");
            continue;
        }
        else
        {
            printf("YES\n");
            for (int i=1;i<=m;i++)if(!a[i])
                printf("%d ",ans[i]);
            puts("");
        }
    }
    return 0;
}