UVA 1623 Enter The Dragon

题意：

　　一只龙，在每个不下雨的日子都可以喝干一个湖里的水，当湖满时，再向这个湖里下雨就会溢出。给出下雨的顺序，求龙喝水的序列。

分析：

　　记录每个湖上次满水的日子，和不下雨的日子。下雨时，查找当前湖上次灌满的日子之后有没有不下雨的日子，让龙在离上次灌满最近的一天喝光那个湖的水。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int n,m;
const int maxn=1000010;
set<int>day;
int ans[maxn];
int full[maxn];
int pos;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        pos=0;
        scanf("%d%d",&n,&m);
        int i,j;
        int flag=1;
        memset(ans,0,sizeof(ans));
        memset(full,0,sizeof(full));
        day.clear();
        for(i=0;i<m;i++)
        {
            int k;
            scanf("%d",&k);
            if(flag==0)
                continue;
            if(k==0)
                day.insert(i);
            else
            {
                ans[i]=-1;
                set<int>::iterator it=day.lower_bound(full[k]);
                if(it==day.end())
                    flag=0;
                else
                {
                    ans[*it]=k;
                    full[k]=i;
                    day.erase(*it);
                }
            }
        }
        if(flag==0)
            printf("NO\n");
        else
        {
            int flag1=1;
             printf("YES\n");
             for(i=0;i<m;i++)
             {
                 if(ans[i]>=0)
                 {
                     if(flag1==1)
                        printf("%d",ans[i]);
                     else
                        printf(" %d",ans[i]);
                     flag1++;
                 }
             }
             printf("\n");
        }
    }
}

UVA 1623 Enter The Dragon

原文：http://www.cnblogs.com/137033036-wjl/p/4935201.html