CF1474C.Array Destruction
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You found a useless array a of 2n positive integers. You have realized that you actually don't need this array, so you decided to throw out all elements of a.
It could have been an easy task, but it turned out that you should follow some rules:
- In the beginning, you select any positive integer x.
- Then you do the following operation n times:
- select two elements of array with sum equals x;
- remove them from a and replace x with maximum of that two numbers.
For example, if initially a=[3,5,1,2], you can select x=6. Then you can select the second and the third elements of a with sum 5+1=6 and throw them out. After this operation, x equals 5 and there are two elements in array: 3 and 2. You can throw them out on the next operation.
Note, that you choose x before the start and can't change it as you want between the operations.
Determine how should you behave to throw out all elements of a.
你发现了一个无用的、包含 2n 个正整数的数组 a。你意识到实际上并不需要这个数组,因此决定将 a 中的所有元素全部丢弃。
这本应是一项简单的任务,但你发现必须遵循以下规则:
- 最初,你任选一个正整数 x;
- 然后你执行以下操作 n 次:
- 在数组中选出两个和恰好等于 x 的元素;
- 将它们从 a 中移除,并将 x 更新为这两个数中的较大值。
例如,若初始时 a=[3,5,1,2],你可以选择 x=6。接着你可以选出 a 中第二和第三个元素(即 5 和 1),因为它们的和为 5+1=6,并将它们丢弃。该操作后,x 变为 5,数组中剩下两个元素:3 和 2。在下一次操作中,你便可将它们一并丢弃。
注意:你必须在操作开始前选定 x,且在后续操作过程中不能随意更改 x 的值。
请确定应如何操作才能将 a 的所有元素全部丢弃。
输入格式
The first line contains a single integer t (1≤t≤1000) — the number of test cases.
The first line of each test case contains the single integer n (1≤n≤1000).
The second line of each test case contains 2n integers a1,a2,…,a2n (1≤ai≤106) — the initial array a.
It is guaranteed that the total sum of n over all test cases doesn't exceed 1000.
第一行包含一个整数 t(1≤t≤1000)—— 表示测试用例的数量。
每个测试用例的第一行包含一个整数 n(1≤n≤1000)。
每个测试用例的第二行包含 2n 个整数 a1,a2,…,a2n(1≤ai≤106)—— 表示初始数组 a。
保证所有测试用例中 n 的总和不超过 1000。
输出格式
For each test case in the first line print YES if it is possible to throw out all elements of the array and NO otherwise.
If it is possible to throw out all elements, print the initial value of x you've chosen. Print description of n operations next. For each operation, print the pair of integers you remove.
对于每个测试用例,在第一行输出 YES(如果可以将数组中的所有元素全部移除),否则输出 NO。
如果可以将所有元素全部移除,则输出你所选择的初始值 x。接下来输出 n 次操作的描述。对于每次操作,输出你所移除的一对整数。
输入输出样例
输入#1
4 2 3 5 1 2 3 1 1 8 8 64 64 2 1 1 2 4 5 1 2 3 4 5 6 7 14 3 11
输出#1
YES 6 1 5 2 3 NO NO YES 21 14 7 3 11 5 6 2 4 3 1
说明/提示
The first test case was described in the statement.
In the second and third test cases, we can show that it is impossible to throw out all elements of array a.
第一个测试用例已在题目描述中给出。
在第二和第三个测试用例中,我们可以证明无法将数组 a 的所有元素都移除。
输入解题思路,AI测评打分。不知道怎么写?