CF1474C.Array Destruction

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

You found a useless array aa of 2n2n positive integers. You have realized that you actually don't need this array, so you decided to throw out all elements of aa.

It could have been an easy task, but it turned out that you should follow some rules:

  1. In the beginning, you select any positive integer xx.
  2. Then you do the following operation nn times:
    • select two elements of array with sum equals xx;
    • remove them from aa and replace xx with maximum of that two numbers.

For example, if initially a=[3,5,1,2]a = [3, 5, 1, 2], you can select x=6x = 6. Then you can select the second and the third elements of aa with sum 5+1=65 + 1 = 6 and throw them out. After this operation, xx equals 55 and there are two elements in array: 33 and 22. You can throw them out on the next operation.

Note, that you choose xx 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 aa.

你发现了一个无用的、包含 2n2n 个正整数的数组 aa。你意识到实际上并不需要这个数组,因此决定将 aa 中的所有元素全部丢弃。

这本应是一项简单的任务,但你发现必须遵循以下规则:

  1. 最初,你任选一个正整数 xx;
  2. 然后你执行以下操作 nn 次:
    • 在数组中选出两个和恰好等于 xx 的元素;
    • 将它们从 aa 中移除,并将 xx 更新为这两个数中的较大值。

例如,若初始时 a=[3,5,1,2]a = [3, 5, 1, 2],你可以选择 x=6x = 6。接着你可以选出 aa 中第二和第三个元素(即 55 和 11),因为它们的和为 5+1=65 + 1 = 6,并将它们丢弃。该操作后,xx 变为 55,数组中剩下两个元素:33 和 22。在下一次操作中,你便可将它们一并丢弃。

注意:你必须在操作开始前选定 xx,且在后续操作过程中不能随意更改 xx 的值。

请确定应如何操作才能将 aa 的所有元素全部丢弃。

输入格式

The first line contains a single integer tt (1≤t≤10001 \leq t \leq 1000) — the number of test cases.

The first line of each test case contains the single integer nn (1≤n≤10001 \leq n \leq 1000).

The second line of each test case contains 2n2n integers a1,a2,…,a2na_1, a_2, \dots, a_{2n} (1≤ai≤1061 \leq a_i \leq 10^6) — the initial array aa.

It is guaranteed that the total sum of nn over all test cases doesn't exceed 10001000.

第一行包含一个整数 tt(1≤t≤10001 \leq t \leq 1000)—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤10001 \leq n \leq 1000)。

每个测试用例的第二行包含 2n2n 个整数 a1,a2,…,a2na_1, a_2, \dots, a_{2n}(1≤ai≤1061 \leq a_i \leq 10^6)—— 表示初始数组 aa。

保证所有测试用例中 nn 的总和不超过 10001000。

输出格式

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 xx you've chosen. Print description of nn operations next. For each operation, print the pair of integers you remove.

对于每个测试用例,在第一行输出 YES(如果可以将数组中的所有元素全部移除),否则输出 NO。

如果可以将所有元素全部移除,则输出你所选择的初始值 xx。接下来输出 nn 次操作的描述。对于每次操作,输出你所移除的一对整数。

输入输出样例

  • 输入#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 aa.

第一个测试用例已在题目描述中给出。

在第二和第三个测试用例中,我们可以证明无法将数组 aa 的所有元素都移除。

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

首页