CF2273A.Lavencia Oranges
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
René is leaving Lavencia after two long, cold years, with n Lavencia oranges and n bags for the oranges (initially empty), both numbered from 1 to n. René packs the oranges according to an array a: orange i goes into bag ai.
Lavencia has a regulatory process for exports. Jacqueline carries it out: she chooses an integer s and confiscates all bags holding exactly s oranges, picking whichever s takes the most oranges from René. The cost of a is the number of oranges Jacqueline confiscates.
More formally, for a given array a, let ci be the number of elements that appear exactly i times in a. The cost of a is: $ \max_{0 \le i \le n} i \cdot c_i $
Given n, find an array a that minimizes the cost.
雷内将在拉文西亚度过漫长而寒冷的两年后离开,他带着 n 个拉文西亚橙子和 n 个空袋子(均从 1 编号至 n)。雷内依照一个数组 a 来装橙子:第 i 个橙子被放入第 ai 个袋子中。
拉文西亚对出口货物有一套监管流程,由雅克琳负责执行:她选择一个整数 s,并没收所有恰好装有 s 个橙子的袋子;她会选择使雷内损失橙子总数最多的那个 s。数组 a 的“代价”即为雅克琳所没收的橙子总数。
更形式化地,对于给定的数组 a,令 ci 表示在 a 中恰好出现 i 次的元素个数。则 a 的代价定义为:
$ \max_{0 \le i \le n} i \cdot c_i $
给定 n,请构造一个数组 a,使其代价最小。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The only line of each test case contains a single integer n (1≤n≤2⋅105).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是测试用例的描述。
每个测试用例仅有一行,包含一个整数 n(1≤n≤2⋅105)。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
For each test case, output two lines.
On the first line, output a single integer — the minimum possible cost.
On the second line, output n integers a1,a2,…,an (1≤ai≤n) — any array that achieves this minimum.
对于每个测试用例,输出两行。
第一行输出一个整数——最小可能的代价。
第二行输出 n 个整数 a1,a2,…,an(其中 1≤ai≤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 1, 1, 2, and 0 oranges into the four bags, respectively. If Jacqueline picks size 1, she confiscates bags 1 and 2, and René loses 2 oranges. If she picks size 2, she confiscates bag 3, and he again loses 2. Therefore, the cost is 2. It can be proved that this is the minimum cost for this test case.
In the second test case, bag 1 holds 2 oranges, bag 2 holds 3, and the other bags are empty. Picking size 2 costs René 2 oranges, and picking size 3 costs him 3, so the cost is 3. It can be proved that, in this case, 3 is the minimum cost.
在第一个测试用例中,René 分别在四个袋子中放入 1、1、2 和 0 个橙子。若 Jacqueline 选择尺寸 1,她将没收第 1 号和第 2 号袋子,René 将损失 2 个橙子;若她选择尺寸 2,她将没收第 3 号袋子,René 同样损失 2 个橙子。因此,代价为 2。可以证明,这是该测试用例的最小代价。
在第二个测试用例中,第 1 号袋子装有 2 个橙子,第 2 号袋子装有 3 个橙子,其余袋子为空。选择尺寸 2 会使 René 损失 2 个橙子,而选择尺寸 3 则会使他损失 3 个橙子,因此代价为 3。可以证明,在本例中,3 是最小代价。
输入解题思路,AI测评打分。不知道怎么写?