CF1512D Corrupted Array 题解
Link
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 <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 300010
void 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;
}