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

题目大意: 给定一个长度为n的全为0的字符串, 每次找出一个长度最大的全为0子区间(如果多个区间长度均为最大值, 则选择最左区间), 若区间长度为奇数, 则将\(a[\frac{l+r}{2}] := i\), 为偶数, 则\(a[\frac{l+r-1}{2}] := i\)
解题思路: 将问题划分为若干个子区间递归求解. 用pair维护每个点的权值以及坐标. 对任意一段全0区间上的中间点, 其权值应为这个点所在区间的左端点减去右端点的差值. 之后对所有点按照权值从小到大进行排序, 最后对排序后的点从1~n赋值即可.

/*
 * @Author: Hellcat
 * @Date: 2020-05-26 14:30:06
 * D. Constructing the Array
 * https://codeforces.com/contest/1353/problem/D
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
pair<int, int> a[N];
int res[N];

void build(int l, int r) {
    if(l > r) return;
    int mid = l+r>>1;
    a[mid].first = l - r;
    a[mid].second = mid;
    build(l, mid-1), build(mid+1, r);
}

int main() {
    int T; cin>>T;
    while(T--) {
        int n; cin>>n;
        build(1, n);
        sort(a+1, a+n+1);
        for(int i = 1; i <= n; i++)
            res[a[i].second] = i;
        for(int i = 1; i <= n; i++)
            cout<<res[i]<<" ";
        puts("");
    }
}

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

原文：https://www.cnblogs.com/tedukuri/p/12970290.html