Blackboard List

题面翻译

在黑板上有两个数字，进行如下操作 $n-2$ 次：

每次在黑板上选择任意两个数，将两个数的差的绝对值写在黑板上。

这样你会得到一个长度为 $n (3 \le n \le 100)$ 的序列。

一共 $t (1 \le t \le 100)$ 组数据。

每组数据给定操作后的序列，需要你还原出最初写在黑板上的两个数。

虽然可能有多个答案，不过，你只需要输出其中任意一个可能中的一个数即可。

题目描述

Two integers were written on a blackboard. After that, the following step was carried out $ n-2 $ times:

Select any two integers on the board, and write the absolute value of their difference on the board.

After this process was complete, the list of $ n $ integers was shuffled. You are given the final list. Recover one of the initial two numbers. You do not need to recover the other one.

You are guaranteed that the input can be generated using the above process.

输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 100 $ ) — the size of the final list.

The next line of each test case contains $ n $ integers $ a_1, a_2, \ldots a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — the shuffled list of numbers written on the blackboard.

It is guaranteed that the input was generated using the process described above.

输出格式

For each test case, output a single integer $ x $ — one of the two initial numbers on the blackboard.

If there are multiple solutions, print any of them.

样例 #1

样例输入 #1

9
3
9 2 7
3
15 -4 11
4
-9 1 11 -10
5
3 0 0 0 3
7
8 16 8 0 8 16 8
4
0 0 0 0
10
27 1 24 28 2 -1 26 25 28 27
6
600000000 800000000 0 -200000000 1000000000 800000000
3
0 -1000000000 1000000000

样例输出 #1

分析

记最开始给定的两个数是 $a$ 和 $b$, 首先我们要明确, 除了 $a$ 和 $b$ 之外, 其他的都只会是非负数, 所以如果有负数, 那么它肯定是 $a$ 和 $b$ 之一

剩下一种情况就是 $a$ 和 $b$ 都是非负数, 我们注意到一个性质, 当 $a$ 和 $b$ 均大于等于0的时候, $\left | a-b \right | $ 肯定要比 $a$ 和 $b$ 中较大的那个小, 由此不难推广到整个序列中任意一个构造出来的数都会比 $max(a,b)$ 要小, 那么整个序列中最大的数肯定就是 $a$ 和 $b$ 其中之一

综上, 我们直接把给定序列升序排列, 第一个是负数就输出第一个, 否则就输出最后一个

我居然想出来了, 看来刷题还是有点用的哈, 这要是放一开始我可能就去看答案了

代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[110];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		int n; cin >> n;
		for(int i = 0; i < n; i++)
			cin >> a[i];
		sort(a, a + n);
		if(a[0] < 0) cout << a[0] << endl;
		else cout << a[n - 1] << endl;
 	}
}

JZTXT

CF1838A