題意：有n個(gè)裝滿水的湖，可以預(yù)知將來(lái)m天下雨情況，每次下滿一個(gè)湖，或者不下，不下雨的時(shí)候可以讓某個(gè)湖變干，問(wèn)是否存在一種方案使得每次下雨之前湖總是干的。

思路：貪心。什么時(shí)候下雨，就什么時(shí)候在下雨之前把湖變干。實(shí)際上就是找該湖上一次滿后的第一個(gè)不下雨的日子來(lái)把它變干。

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("");}} }

總結(jié)

以上是生活随笔為你收集整理的uva 1623——Enter The Dragon的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。