101487E - Enter The Dragon

思路:做的时候两个地方理解错了,第一个事我以为龙吸了水,水就干了,其实龙是在下雨之前吸的,下雨时湖水又满了,所以湖水永远不会干;第二个是以为只要找前面一段没下雨的天吸水就可以了,其实是上一次满了之后没下雨的天吸水都可以。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e6+;
set<int>s;
int a[N];
int ans[N];
int pre_full_pos[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=;i<m;i++)cin>>a[i];
s.clear();
mem(pre_full_pos,);
mem(ans,);
bool flag=false;
for(int i=;i<m&&!flag;i++)
{
if(a[i])
{
set<int>::iterator it=s.lower_bound(pre_full_pos[a[i]]);
if(it!=s.end())
{
ans[*it]=a[i];
s.erase(it);
pre_full_pos[a[i]]=i;
}
else flag=true;
}
else s.insert(i);
}
if(flag){
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
for(int i=;i<m;i++)if(!a[i])cout<<ans[i]<<' ';
cout<<endl;
}
return ;
}
/*
10
4 10
0 0 3 4 0 0 1 0 4 3
*/
05-12 11:36