救命!76分wa了
查看原帖
救命!76分wa了
388414
comcopy楼主2022/7/15 18:52

用贪心做的,分别用大根堆和优先队列维护

本来想着分两个队列,过去不行的石头就放到回来上,回来也不行就直接输出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;
}
2022/7/15 18:52
加载中...