有一只龙，在每个不下雨的日子都可以喝干一个湖里的水，当湖满时，再向这个湖里下雨就会溢出。给出下雨的顺序，求龙喝水的序列。
记录每个湖上次满水的日子，和不下雨的日子。下雨时，查找当前湖最后灌满的日子之后有没有不下雨的日子，让龙在最近的一天喝光那个湖的水。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int maxn=1000010;
int n,m,pos,ans[maxn],full[maxn];
set<int> d;
int main(){
int t;
scanf("%d",&t);
while(t--){
bool flag=true;
pos=0;
d.clear();
memset(ans,0,sizeof(ans));
memset(full,0,sizeof(full));
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){
int k;
scanf("%d",&k);
if(!flag) continue;
if(!k) d.insert(i);
else{
ans[i]=-1;
set<int>::iterator it=d.lower_bound(full[k]);
if(it==d.end()) flag=false;
else{
ans[*it]=k;
full[k]=i;
d.erase(*it);
}
}
}
if(!flag) printf("NO\n");
else{
bool first=true;
printf("YES");
for(int i=0;i<m;++i)
if(ans[i]>=0)
printf("%c%d",first?(first=false,'\n'):' ',ans[i]);
printf("\n");
}
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **