传送门
题意： 现有一个长度为n的初始数组a(其值全为0)，对其进行n次操作。每次从左往右选取其连续为0的最大子段进行如下两类操作：
- 若r - l + 1为偶数，那么a[(l + r) / 2] := i.
- 若r - l + 1为奇数，那么a[(l + r - 1) / 2] := i.
其中 i 表示第 i 次操作。最后输出答案数组a(该数组存在且唯一)。
思路：
- 可以利用机构图定义一个新类型，该类型代表连续为0的小区间，其具有区间的左右边界l，r和区间的长度len.
- 利用优先队列排序，按照长度降序排列，长度相等的按照左边界l的升序排列。
- 每次取队头进行处理，每次找到相应的a[pos]赋值为 i ，再将pos分成的两个新的连续0子段加入队列中。
代码实现：
#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
using namespace std;
const int inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;int t, n, a[N];struct node{
int l,r,len;//重载运算符bool operator < (const node&next )const{
if(len == next.len) return l > next.l;return len < next.len;}
};priority_queue<node> q;signed main()
{
cin >> t;while(t --){
cin >> n;while(!q.empty()) q.pop();q.push((node){
1, n, n});int cnt = 0;while(true){
//取出队头node top = q.top(); q.pop();int l = top.l, r = top.r, pos;//找到相应位置赋值if((r - l + 1) % 2){
a[(l + r) >> 1] = ++ cnt;pos = (l + r) >> 1;}else{
a[(l + r - 1) >> 1] = ++ cnt;pos = (l + r - 1) >> 1;}if(cnt == n) break; //n次操作已进行完//将新产生的子段加入队列if(pos - 1 >= l) q.push((node){
l, pos - 1, pos - l});if(r >= pos + 1) q.push((node){
pos + 1, r, r - pos});}//最后自己输出答案数组for(int i = 1; i <= n; i ++)cout << a[i] << " ";cout << endl;}return 0;
}