SUBTASK1 TLE QAQ

优先队列实现第二问

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
struct mi{
    int h,pos;
    bool operator >(const mi &a)const{
        return h>a.h;
    }
};
priority_queue<mi,vector<mi>,greater<mi>> pq;//从小到大排列的优先队列
queue<int> tst;//缓存数据给优先队列用
int main(){
    // freopen("ans.in","r",stdin);
    int minn=1e9;
    int t,cnt=0,bcnt=0;
    int tpoint=0,mpoint=0;
    int acnt=0,a[114514],b[114514];
    while(cin>>t){
        //解决第一问的同时缓存数据给第二问
        tst.push(t);
        a[++acnt]=t;
        if(bcnt==0||a[acnt]<=b[bcnt]){ 
            bcnt++;
            b[bcnt]=a[acnt];
            
        }
        else{
            int l=1;
            int r=bcnt;
            while(l<r){//二分查询边界交接
                int mid=(l+r)>>1;
                if(b[mid]<a[acnt]){
                    r=mid;
                }else l=mid+1;
            }
            b[l]=a[acnt];
        }
    }
    cout<<bcnt<<endl;
    while(!tst.empty()){
        //cnt是系统的数量
        t=tst.front();
        tst.pop();
        //以下为优先队列输出第二行的答案 复杂度O(nlogn)？自己算的
        if(pq.empty()){//如果一开始是空的
            mi ttemp;
            ttemp.h=t;
            pq.push(ttemp);//推进去
            cnt++;
            continue;
        }
        if(pq.top().h>=t){//如果最小的能hold住高度，更新高度
            mi ttemp;
            ttemp=pq.top();
            ttemp.h=t;
            pq.pop();
            pq.push(ttemp);
        }
        if(pq.top().h<t){//如果最小的都hold不住高度
            mi temp[pq.size()];//缓存队列内容
            while(pq.top().h<t){//删顶找合适的，不合适直接删完
                if(pq.empty()){break;}
                temp[tpoint]=pq.top();
                pq.pop();
                tpoint++;
            }
            tpoint--;//因为我把++放最后了
            if(pq.empty()){//如果一个都没有，创建一个
                mi ttemp;
                // cout<<"< BUT EMPTY"<<endl;
                cnt++;
                ttemp.h=t;
                pq.push(ttemp);
            }
            else if(pq.top().h>=t){//如果找到了就更新
                // cout<<"FIND > "<<pq.top().h<<" AFT CHANGE "<<t<<endl;
                mi ttemp;
                ttemp=pq.top();
                ttemp.h=t;
                // ttemp.prcnt++;
                // cout<<"AFT CHANGE PRCNT "<<ttemp.prcnt<<endl;
                pq.pop();
                pq.push(ttemp);
            }
            while(tpoint>=0){//把原来的都放回去
                // cout<<"PUSH "<<temp[tpoint].h<<" into queue"<<endl;
                if(tpoint==0){
                    pq.push(temp[tpoint]);
                    break;
                }
                pq.push(temp[tpoint]);
                tpoint--;
            }
        }
    }
    // int maxx=-1;
    // while(!pq.empty()){
    //     maxx=max(pq.top().prcnt,maxx);
    //     pq.pop();
    // }
    cout<<cnt;//输出cnt
    return 0;
}