CF1512D Corrupted Array 题解

Link

洛谷

【资料图】

Codeforces

Description

给定一个正整数 \(n\) 和长度为 \(n+2\) 的数组 \(b\)，数组 \(b\) 是依据如下算法构造的：

• 随机生成一个含有 \(n\) 个元素的原始数组\(a\)；
• 把数组 \(a\) 赋值给数组 \(b\)，即 \(b_i=a_i(1\le i\le n)\)；
• 数组 \(b\) 的第 \(n+1\) 个元素为数组 \(a\) 的元素和，即 \(b_{n+1}=\sum_{i=1}^na_i\)；
• 数组 \(b\) 的第 \(n+2\) 个元素是个随机整数 \(x(1\le x\le10^9)\)；
• 打乱 \(b\) 数组。

例如，数组 \(b=[2,3,7,12,2]\)，那么它能够通过如下方式构建：

• \(a=[2,2,3]\)，且 \(x=12\)；
• \(a=[3,2,7]\)，且 \(x=2\)。

给定一个 \(b\) 数组，请你求出它对应的 \(a\) 数组。

Solution

假设打乱前的 \(b\) 数组为 \(c\)，记所有数的和为 \(sum\)。

将 \(b\) 数组排序，为了满足数组 \(c\) 的第 \(n+1\) 个元素为数组 \(a\) 的元素和，和一定为最大的数或第二大的数（此时对应的随机数为最大的数）。

在排序后的 \(b\) 数组中枚举随机数，设当前位置为 \(i\)。

• 当 \(i = n + 2\) 时，\(sum - b_{n + 2} - b_{n + 1} = b_{n + 1}\) 时满足条件，此时输出 \(b_{1},\ldots,b_{n}\) 即可。

• 否则当 \(sum - b_{n + 2} - b_{i} = b_{n + 2}\) 时满足条件，此时对于所有的 \((1 \leq k \leq n + 1)\) 且 \(k \ne i\) 输出 \(b_{k}\) 即可。

全部枚举仍无答案则无解。

Codes

#include using namespace std;#define int long long#define max_n 300010void read(int &p){    p = 0;    int k = 1;    char c = getchar();    while (c < "0" || c > "9")    {        if (c == "-")        {            k = -1;        }        c = getchar();    }    while (c >= "0" && c <= "9")    {        p = p * 10 + c - "0";        c = getchar();    }    p *= k;    return;}void write_(int x){    if (x < 0)    {        putchar("-");        x = -x;    }    if (x > 9)    {        write_(x / 10);    }    putchar(x % 10 + "0");}void writesp(int x){    write_(x);    putchar(" ");}void writeln(int x){    write_(x);    putchar("\n");}int T, n, nums[max_n];signed main(){#if _clang_    freopen("1.in", "r", stdin);    freopen("1.out", "w", stdout);#endif    read(T);    while (T--)    {        read(n);        int sum = 0;        for (int i = 1; i <= n + 2; i++)        {            read(nums[i]);            sum += nums[i];        }        sort(nums + 1, nums + n + 3);        if (sum - nums[n + 2] - nums[n + 1] == nums[n + 1] || sum - nums[n + 2] - nums[n + 1] == nums[n + 2])        {            for (int i = 1; i <= n; i++)            {                writesp(nums[i]);            }            puts("");            continue;        }        int ans = -1;        for (int i = 1; i <= n; i++)        {            if (sum - nums[n + 2] - nums[i] == nums[n + 2])            {                ans = i;                continue;            }        }        if (ans == -1)        {            puts("-1");            continue;        }        else        {            for (int i = 1; i <= n + 1; i++)            {                if (i == ans)                {                    continue;                }                writesp(nums[i]);            }            puts("");        }    }    return 0;}