Skip to content

CodeForces 1353 D. Constructing the Array#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1 second

Memory Limit: 256 megabytes

1.2. Problem Description#

You are given an array of length consisting of zeros. You perform actions with this array: during the -th action, the following sequence of operations appears:

Consider the array of length (initially ). Then it changes as follows:

  1. Firstly, we choose the segment and assign , so becomes ;
  2. then we choose the segment and assign , so becomes ;
  3. then we choose the segment and assign , so becomes ;
  4. then we choose the segment and assign , so becomes ;
  5. and at last we choose the segment and assign , so becomes .

Your task is to find the array of length after performing all actions. Note that the answer exists and unique.

You have to answer independent test cases.

1.3. Input#

The first line of the input contains one integer () — the number of test cases. Then test cases follow.

The only line of the test case contains one integer () — the length of .

It is guaranteed that the sum of over all test cases does not exceed ().

1.4. Onput#

For each test case, print the answer — the array of length after performing actions described in the problem statement. Note that the answer exists and unique.

1.5. Sample Input#

6
1
2
3
4
5
6

1.6. Sample Onput#

1
1 2
2 1 3
3 1 2 4
2 4 1 3 5
3 4 1 5 2 6

1.7. Source#

CodeForces 1353 D. Constructing the Array

2. 解读#

用优先队列 priority_queue 根据区间长度构造大顶堆。

每次取出堆顶的区间元素进行赋值，每次赋值完以后，将左子区间和右子区间放入堆中。和分治法的思想比较类似。

重复以上步骤直到堆为空。

3. 代码#

#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

const long long num = 2 * 1e5 + 1;
using namespace std;
// 定义数据类型
#define llpair pair<long long, long long>
// 存储
long long list[num];
// 标记当前数字个数
long long markNum;
// 队列长度
long long n;
// 定义排序方法
struct cmp {
    bool operator()(llpair a, llpair b)
    {
        if ((a.second - a.first) != (b.second - b.first)) {
            // 返回小于判断时，是大顶堆，与queue相反
            return (a.second - a.first) < (b.second - b.first);
        } else {
            // 返回大于号时，较小的元素在前
            return a.first > b.first;
        }
    }
};
// 使用优先队列构造大顶堆
priority_queue<llpair, vector<llpair>, cmp> qu;
// 定义清零函数
void clear(priority_queue<llpair, vector<llpair>, cmp>& q)
{
    priority_queue<llpair, vector<llpair>, cmp> empty;
    swap(empty, q);
}

// 分治法
void divideAndConquer(long long array[])
{
    while (!qu.empty()) {
        // 获取最大区间
        llpair pairBuffer = qu.top();
        // 出队
        qu.pop();
        // 获取队首元素
        long long low = pairBuffer.first;
        long long high = pairBuffer.second;
        // 计算中值
        long long mid = low + (high - low) / 2;
        if (low <= high && mid > 0 && array[mid] == 0) {
            array[mid] = markNum;
            markNum++;
        }
        // 入队
        if (low <= mid - 1)
            qu.push(make_pair(low, mid - 1));
        if (mid + 1 <= high)
            qu.push(make_pair(mid + 1, high));
    }
}

int main()
{
    // test case
    long long t;
    // long long n;
    // test case
    scanf("%lld", &t);
    // for each test case
    while (t--) {
        // 初始化
        markNum = 1;
        memset(list, 0, sizeof(list));
        clear(qu);
        // 输入
        scanf("%lld", &n);
        // 计算
        qu.push(make_pair(1, n));
        divideAndConquer(list);
        // 输出
        for (int i = 1; i <= n; i++) {
            printf("%lld ", list[i]);
        }
        printf("\n");
    }
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top