2020 7月最后一题

港控/mmm° 2022-12-01 15:47 81阅读 0赞

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int n,m;
    struct Node{ 
        int lev,v;
        bool operator <(const Node&a)const{ 
            return lev!=a.lev?lev>a.lev:v>a.v;
        }
    };
    priority_queue<Node,vector<Node>>q;
    vector<int>ans[maxn];
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        cin>>n>>m;
        for(int t,i=0;i<m&&q.size()<m;++i){ 
            cin>>t;
            q.push({ 0,t});
        }
        for(int t,i=m;i<n;++i){ 
            cin>>t;
            Node top=q.top();
            q.pop();
            ans[top.lev].push_back(top.v);
            if(t<top.v)q.push({ top.lev+1,t});
            else q.push({ top.lev,t});
        }
        while (!q.empty()){ 
            Node top=q.top();
            q.pop();
            ans[top.lev].push_back(top.v);
        }
        for(int i=0;ans[i].size();i++){ 
            bool flag=false;
            for(int x:ans[i]){ 
                if(flag)cout<<' ';
                else flag=true;
                cout<<x;
            }
            cout<<endl;
        }
        return 0;
    }

最后一个点不过版本：

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100010;
    int n,m,a[maxn];
    priority_queue<int,vector<int>,greater<int>>q;
    bool vis[maxn];
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i){ 
            scanf("%d",&a[i]);
        }
        int cnt=0;
        while (cnt<n){ 
            bool flag=false;
            int i;
            for(i=0;q.size()<m&&i<n;++i){ 
                if(!vis[i]){ 
                    if(q.size()<m){ 
                        q.push(a[i]);
                        vis[i]=true;
                    }
                }
            }
            for(;i<n&&!q.empty();++i) { 
                int top=q.top();
                if(!vis[i]&&a[i]>top){ 
                    q.pop();
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<top;
                    cnt++;
                    q.push(a[i]);
                    vis[i]=true;
                }
            }
            while (!q.empty()){ 
                int top=q.top();
                q.pop();
                if(flag)cout<<' ';
                else flag=true;
                cout<<top;
                cnt++;
            }
            cout<<endl;
        }
        return 0;
    }