用贪心做的,分别用大根堆和优先队列维护
本来想着分两个队列,过去不行的石头就放到回来上,回来也不行就直接输出NO,但不知道为什么,Wa了6个点
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int w[100010];
queue<int>q;
priority_queue<int>q1;
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=m;++i)
{
cin>>w[i];
}
if(m==0)
{
if(n<s) cout<<"NO"<<endl;
else cout<<"YES"<<endl<<1<<" "<<0<<endl;
return 0;
}
if(n<s)
{
cout<<"NO"<<endl;
return 0;
}
int now;
bool t=true;
q.push(0);
w[m+1]=n;
q1.push(m+1);
for(int i=1;i<=m;++i)
{
if(w[i]-w[q.back()]<s)
{
if(q1.empty()) q1.push(i);
else
if(w[i]-w[q1.top()]<s)
{
t=false;
break;
}
else q1.push(i);
}
else q.push(i);
}
if(!t)
{
cout<<"NO"<<endl;
return 0;
}
else
{
cout<<"YES"<<endl;
while(!q.empty())
{
if(q.front()==0) q.pop();
cout<<q.front()<<" ";
q.pop();
}
while(!q1.empty())
{
cout<<q1.top()<<" ";
q1.pop();
}
cout<<"0"<<endl;
}
return 0;
}