uva 1623——Enter The Dragon

以你之姓@ 2022-08-09 16:42 167阅读 0赞

题意：有n个装满水的湖，可以预知将来m天下雨情况，每次下满一个湖，或者不下，不下雨的时候可以让某个湖变干，问是否存在一种方案使得每次下雨之前湖总是干的。

思路：贪心。什么时候下雨，就什么时候在下雨之前把湖变干。实际上就是找该湖上一次满后的第一个不下雨的日子来把它变干。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000005;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define fr(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int v[N],la[N],s[N];
    set<int>ep;
    set<int>::iterator p;
    int main()
    {
        int T,n,m,f;
        scanf("%d",&T);
        while (T--)
        {
            cls(s,0);cls(la,0);f=0;
            ep.clear();
            scanf("%d %d",&n,&m);
            fr(i,0,m-1)
            {
                scanf("%d",&v[i]);
                if (f) continue;
                if (!v[i]) ep.insert(i);//cout<<i<<endl;
                else
                {
                    p=ep.lower_bound(la[v[i]]);
                    if (p==ep.end()) f=1;
                    else
                    {
                        //cout<<*p<<endl;
                        s[*p]=v[i];
                        la[v[i]]=i;
                        ep.erase(p);
                    }
                }
            }
            if (f) puts("NO");
            else
            {
                puts("YES");
                fr(i,0,m-1)
                {
                    if (!v[i]) printf("%d ",s[i]);
                }
                puts("");
            }
        }
    }