Codeforces Round #642 (Div. 3) D. Constructing the Array

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn =2e5+5;
 5 int ans[maxn];
 6 struct node
 7 {
 8     int l,r;
 9     bool operator<(const node& a)const //重载小于号
10     {
11         int s1=r-l+1;
12         int s2=a.r-a.l+1;
13         if(s1==s2) return a.l<l;     //相同就取左边   //重载规则让a.l在左边 然后a.l<l 就是小的排前面
14         //else return a.r-a.l+1>r-l+1;          //两种重载是一样的
15         else return s2>s1;      //不同就长的优先
16     }
17 };
18 int main()
19 {
20     ios::sync_with_stdio(false);
21     cin.tie(0);
22     int t;
23     cin>>t;
24     while(t--)
25     {
26         int n;
27         cin>>n;
28         int tot=0;
29         priority_queue<node>q;
30         q.push({1,n});
31         while(!q.empty())
32         {
33             node u=q.top();
34             q.pop();
35             int mid=(u.l+u.r)/2;
36             ans[mid]=++tot;
37             if(mid+1<=u.r) //在当前的区间内分裂
38             {
39                 q.push({mid+1,u.r});
40             }
41             if(mid-1>=u.l)
42             {
43                 q.push({u.l,mid-1});
44             }
45             /*if(mid+1<=n) 而不是跑到区间之外分裂
46             {
47                 q.push({mid+1,n});
48             }                         // 错的写法 如[2,2]这种区间永远得不到
49             if(mid-1>=1)
50             {
51                 q.push(l,mid-1);
52             }*/
53         }
54         for(int i=1;i<=n;i++)
55         {
56             cout<<ans[i]<<" ";
57         }
58         cout<<‘\n‘;
59 
60     }
61 
62         //会被两个区间错写成 (l,mid-1)  (mid+1,n) 然后就错了
63 }