CodeForces - 1353D Constructing the Array

CodeForces - 1353D

这道题也可能比较简单，主要是要想到优先队列要怎么使用，这一点如果用递归会写不了

但是因为对优先队列不太熟悉，只有被提示可以用优先队列才想到要怎么用，

还是很重要的STL

注意运算符的重构应该反着来写

其他的思维很朴素，运算符的重构就是，先比较长度，优先用长度长的，如果一样就是选择左边界小的，用结构体封装数据即可

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[200005]={0};
int cnt=0;
struct Node{
    int l;int r;int val;
};
bool operator<(Node a,Node b){
    if(a.val==b.val) return a.l>b.l;
    return a.val<b.val;
}
priority_queue<Node> q;
void solve(){
    while(!q.empty()){
        Node x=q.top();
        q.pop();
        if(x.val==1){
            a[x.l]=++cnt;
            continue;
        }
        int mid=(x.l+x.r)>>1;
        a[mid]=++cnt;
        Node aa;
        aa.l=x.l;
        aa.r=mid-1;
        aa.val=aa.r-aa.l+1;
        if(aa.val>0) q.push(aa); 
        Node bb;
        bb.l=mid+1;
        bb.r=x.r;
        bb.val=bb.r-bb.l+1;
        if(bb.val>0) q.push(bb);
    }
}
signed main(){
    int time;
    cin>>time;
    while(time--){
        int n;
        cnt=0;
        cin>>n;
        Node u;
        u.l=1;u.r=n;u.val=n;
        q.push(u);
        solve();
        for(int i=1;i<=n;++i){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
}