欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

codeforces 1353D(优先队列)

程序员文章站 2022-09-17 08:26:30
题意描述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 zer...

题意描述

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代码

#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;
}

本文地址:https://blog.csdn.net/weixin_45729946/article/details/108560637