题意描述
You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:
Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one; Let this segment be [l;r]. If r−l 1 is odd (not divisible by 2) then assign (set) a[l r2]:=i (where i is the number of the current action), otherwise (if r−l 1 is even) assign (set) a[l r−12]:=i. Consider the array a of length 5 (initially a=[0,0,0,0,0]). Then it changes as follows:
Firstly, we choose the segment [1;5] and assign a[3]:=1, so a becomes [0,0,1,0,0]; then we choose the segment [1;2] and assign a[1]:=2, so a becomes [2,0,1,0,0]; then we choose the segment [4;5] and assign a[4]:=3, so a becomes [2,0,1,3,0]; then we choose the segment [2;2] and assign a[2]:=4, so a becomes [2,4,1,3,0]; and at last we choose the segment [5;5] and assign a[5]:=5, so a becomes [2,4,1,3,5]. Your task is to find the array a of length n after performing all n actions. Note that the answer exists and unique.
You have to answer t independent test cases.
思路
因为每次要找到长度最长的靠左的0数组，所以我们可以使用优先队列来优化，然后模拟操作即可。
AC代码
代码语言：javascript复制#include<bits/stdc .h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x )
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5 10;
const int M=1e6 10;
const int INF=0x3f3f3f3f;
const int MOD=1e9 7;
int a[N];
struct node{
int l,r,len;
bool operator >(const node& b)const{
if(len!=b.len) return len>b.len;
return l<b.l;
}
bool operator <(const node& b) const{
return !(*this>b);
}
};
void solve(){
int n;cin>>n;
priority_queue<node> pq;
pq.push({1,n,n});
rep(i,1,n 1){
node t=pq.top();pq.pop();
int l=t.l,r=t.r,len=t.len;
if((r-l 1)%2==0){
int idx=(l r-1)/2;
a[idx]=i;
if(idx!=l){
int newl=l,newr=idx-1,newlen=newr-newl 1;
pq.push({newl,newr,newlen});
newl=idx 1,newr=r,newlen=newr-newl 1;
pq.push({newl,newr,newlen});
}else{
int newl=l 1,newr=r,newlen=newr-newl 1;
pq.push({newl,newr,newlen});
}
}else{
int idx=(l r)/2;
a[idx]=i;
if(idx!=l){
int newl=l,newr=idx-1,newlen=newr-newl 1;
pq.push({newl,newr,newlen});
newl=idx 1,newr=r,newlen=newr-newl 1;
pq.push({newl,newr,newlen});
}else{
int newl=l 1,newr=r,newlen=newr-newl 1;
pq.push({newl,newr,newlen});
}
}
}
rep(i,1,n 1) cout<<a[i]<<' ';
cout<<endl;
}
int main(){
IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
