CF2273A.Lavencia Oranges

普及-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

René is leaving Lavencia after two long, cold years, with nn Lavencia oranges and nn bags for the oranges (initially empty), both numbered from 11 to nn. René packs the oranges according to an array aa: orange ii goes into bag aia_i.

Lavencia has a regulatory process for exports. Jacqueline carries it out: she chooses an integer ss and confiscates all bags holding exactly ss oranges, picking whichever ss takes the most oranges from René. The cost of aa is the number of oranges Jacqueline confiscates.

More formally, for a given array aa, let cic_i be the number of elements that appear exactly ii times in aa. The cost of aa is: $ \max_{0 \le i \le n} i \cdot c_i $

Given nn, find an array aa that minimizes the cost.

雷内将在拉文西亚度过漫长而寒冷的两年后离开,他带着 nn 个拉文西亚橙子和 nn 个空袋子(均从 11 编号至 nn)。雷内依照一个数组 aa 来装橙子:第 ii 个橙子被放入第 aia_i 个袋子中。

拉文西亚对出口货物有一套监管流程,由雅克琳负责执行:她选择一个整数 ss,并没收所有恰好装有 ss 个橙子的袋子;她会选择使雷内损失橙子总数最多的那个 ss。数组 aa 的“代价”即为雅克琳所没收的橙子总数。

更形式化地,对于给定的数组 aa,令 cic_i 表示在 aa 中恰好出现 ii 次的元素个数。则 aa 的代价定义为:
$ \max_{0 \le i \le n} i \cdot c_i $

给定 nn,请构造一个数组 aa,使其代价最小。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The only line of each test case contains a single integer nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是测试用例的描述。

每个测试用例仅有一行,包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, output two lines.

On the first line, output a single integer — the minimum possible cost.

On the second line, output nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤n1 \le a_i \le n) — any array that achieves this minimum.

对于每个测试用例,输出两行。

第一行输出一个整数——最小可能的代价。

第二行输出 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(其中 1≤ai≤n1 \le a_i \le n)——任意一个能达到该最小代价的数组。

输入输出样例

  • 输入#1

    3
    4
    5
    8

    输出#1

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

说明/提示

In the first test case, René places 11, 11, 22, and 00 oranges into the four bags, respectively. If Jacqueline picks size 11, she confiscates bags 11 and 22, and René loses 22 oranges. If she picks size 22, she confiscates bag 33, and he again loses 22. Therefore, the cost is 22. It can be proved that this is the minimum cost for this test case.

In the second test case, bag 11 holds 22 oranges, bag 22 holds 33, and the other bags are empty. Picking size 22 costs René 22 oranges, and picking size 33 costs him 33, so the cost is 33. It can be proved that, in this case, 33 is the minimum cost.

在第一个测试用例中,René 分别在四个袋子中放入 11、11、22 和 00 个橙子。若 Jacqueline 选择尺寸 11,她将没收第 11 号和第 22 号袋子,René 将损失 22 个橙子;若她选择尺寸 22,她将没收第 33 号袋子,René 同样损失 22 个橙子。因此,代价为 22。可以证明,这是该测试用例的最小代价。

在第二个测试用例中,第 11 号袋子装有 22 个橙子,第 22 号袋子装有 33 个橙子,其余袋子为空。选择尺寸 22 会使 René 损失 22 个橙子,而选择尺寸 33 则会使他损失 33 个橙子,因此代价为 33。可以证明,在本例中,33 是最小代价。

输入解题思路,AI测评打分。不知道怎么写?

首页