Codeforces题解｜1512D Corrupted Array

题目信息 📚

【题目描述】

You are given a number $n$ and an array $b_1, b_2, \ldots, b_{n+2}$, obtained according to the following algorithm:

Some array $a_1, a_2, \ldots, a_n$ was guessed;
Array $a$ was written to array $b$, i.e., $b_i = a_i$ ($1 \leq i \leq n$);
The $(n+1)$-th element of the array $b$ is the sum of the numbers in the array $a$, i.e., $b_{n+1} = a_1 + a_2 + \ldots + a_n$;
The $(n+2)$-th element of the array $b$ was written some number $x$ ($1 \leq x \leq 10^9$), i.e., $b_{n+2} = x$; The array $b$ was shuffled.

For example, the array $b = [2, 3, 7, 12, 2]$ could be obtained in the following ways:

$a = [2, 2, 3]$ and $x = 12$;
$a = [3, 2, 7]$ and $x = 2$.

For the given array $b$, find any array $a$ that could have been guessed initially.

【输入】

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$). Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

The second row of each test case contains $n+2$ integers $b_1, b_2, \ldots, b_{n+2}$ ($1 \leq b_i \leq 10^9$).

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

【输出】

For each test case, output:

“-1”, if the array $b$ could not be obtained from any array $a$;
$n$ integers $a_1, a_2, \ldots, a_n$, otherwise.

If there are several arrays of $a$, you can output any.

【输入样例1】

4
3
2 3 7 12 2
4
9 1 7 1 6 5
5
18 2 2 3 2 9 2
3
2 6 9 2 1

【输出样例1】

【题目来源】

https://codeforces.com/problemset/problem/1512/D

题目解析 🍉

【题目分析】

思维题。

首先对 b 数组升序排序。

生成的总和一定在 b[n] 或者 b[n-1] 处，根据这两种情况进行枚举判断即可。

若总和在 b[n] 处，则 x 在 b[1] ~ b[n-1] 中某一处
若总和在 b[n-1] 处，则 x 一定在 b[n] 处

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, b[N], s[N];

void solve() {
    cin >> n;
    n += 2;
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(b + 1, b + n + 1);

    // 计算前缀和
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + b[i];
    
    // 总和一定在b[n]或者b[n-1]处

    // 若b[n]为总和，在b[1]~b[n-1]中查找x
    LL res = b[n], sum = s[n - 1] - s[0];
    for (int i = 1; i <= n - 1; i++) {
        // 找到当前x，则输出a数组
        if (sum - b[i] == res) {
            for (int j = 1; j <= n - 1; j++) {
                if (j != i) cout << b[j] << " ";
            }
            cout << endl;
            return;
        }
    }

    // 若b[n-1]为总和，则b[n]一定为x
    res = b[n - 1], sum = s[n - 2] - s[0];
    if (res == sum) {
        for (int i = 1; i <= n - 2; i++) cout << b[i] << " ";
        cout << endl;
    } else {
        cout << -1 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}