博客

Question

给你一个长度为n的全为0的序列，让你从1-n填数，填的位置为找出最长的0序列，如序列长度为奇数，则为（l+r）/2，为偶数，则为（l+r-1）/2

Solution

运用优先队列，将[l,mid-1],[mid,r]push进去，运用重载运算符排序

Code

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define maxn 1005
#define inf 0x3f3f3f
#define endl '\n'
#pragma GCC optimize(2)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long ll;
//ll fpm(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//ll fastPow(ll a,ll b) {ll res=1; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
int t;
int n;
struct node
{
	int l,r,si;
	bool operator > (const node& a) const
	{
		if(si!=a.si){
			return si<a.si;
		}
		return l>a.l;
	}
};
int ans[200050];
int main(){
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
	cin>>n;
	memset(ans,0,sizeof(ans[1]*(n+10)));
	priority_queue<node,vector<node>,greater<node> >q;
	q.push(node{1,n,n});
	int zz=1;
	while(!q.empty()){
		node qq=q.top();
		q.pop();
		int ll=qq.l,rr=qq.r;
		if(ll==rr){
			ans[ll]=zz;
			zz++;
		}
		else{
			if((rr-ll+1)&1){
				int temp=(rr+ll)>>1;
				ans[temp]=zz;
				zz++;
				if(ll<temp){
					q.push(node{ll,temp-1,temp-ll});
				}
				if(temp<rr){
					q.push(node{temp+1,rr,rr-temp});
				}
			}
			else{
				int temp=(ll+rr-1)>>1;
				ans[temp]=zz;
				zz++;
				if(ll<temp){
					q.push(node{ll,temp-1,temp-ll});
				}
				if(temp<rr){
					q.push(node{temp+1,rr,rr-temp});
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
}
	return 0;
}