Codeforces 1353D - Constructing

小区的小滑梯，不知道我这个体型还能不能上去玩。

翻译

构造数组

给你一个长度为 n 元素都是 0 的数组 a。你需要对数组进行 n 次操作，第 i 次的操作序列如下：

1. 选择最大的只由 0 组成的子串，如果有多个长度相同的子串，选择最左边那个。
2. 选择这个字串的中心点，(left + right) / 2 并向下取整，赋值为步数 i。

可以保证答案存在且唯一。

输入格式

第一行输入整数 t，表示测试用例组数。

每个测试用例输入一个整数 n。

可以保证所有的 n 之和不超过 2 * 10 ^ 5。

输出格式

每个测试用例输出一行答案数组，用空格分隔。

分析

每次取中间点，赋值，然后需要将剩下的所有区间放入列表排序。

考虑到这点，这个数据量下，需要logn的思路，也就是考虑使用优先队列，python内置优先队列逻辑。

排序的逻辑就是先比较队列长度，如果相同就比较谁的 left 小。

代码(PyPy3)

# https://codeforces.com/contest/1353/problem/D

import sys
import os
import heapq

try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass

class Node:
    def __init__(self, n, left, right):
        self.left = left
        self.right = right
        self.weight = n - right + left

    def __lt__(self, other):
        return self.weight < other.weight or (self.weight == other.weight and self.left < other.left)

t = int(input())

for _ in range(t):
    n = int(input())

    q = []
    result = [0] * (n + 1)
    heapq.heappush(q, Node(n, 1, n))

    index = 1
    while True:
        if len(q) == 0:
            break

        node = heapq.heappop(q)
        if node is None:
            break
        
        if node.left == node.right:
            result[node.left] = index
            index += 1
        else:
            middle = int((node.left + node.right) / 2)
            result[middle] = index
            index += 1

            if node.left != middle:
                heapq.heappush(q, Node(n, node.left, middle - 1))
            heapq.heappush(q, Node(n, middle + 1, node.right))

    print(" ".join(str(i) for i in result[1:]))

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.05.20 长春