D. Corrupted Array | Round #713 Div.3
5728 ワード
https://codeforces.com/contest/1512/problem/D
2秒、256 MBメモリ
input : t (1 ≤ t ≤ 104) n (1 ≤ n ≤ 2 * 105) b1, b2, …, bn + 2 (1 ≤ bi ≤ 109) output : "-1", if the array b could not be obtained from any array a;
n integers b1, b2, …, bn + 2, otherwise.
bから配列aが得られない場合は「-1」が出力され、そうでない場合は配列aが出力される. 条件:
some array a1, a2, …, an + 2 was guessed;
a配列が存在する.
array a was written to array b, i.e. bi=ai (1≤i≤n);
b配列にa配列が作成されました.
The (n+1)-th element of the array b is the sum of the numbers in the array a, i.e. bn + 2 = a1, a2, …, an;
bのn+1要素はa配列の和である.
The (n+2)-th element of the array b was written some number x (1≤x≤109), i.e. bn+2=x; The
bのn+2要素は任意のxである.
array b was shuffled.
b配列は混合されている.
入力したすべての値を加算すると、この値は2 A+xになります.Aは配列aの和を表す.
bの最大値だから?あるいは,2番目に大きい値はa配列の和であるため,2回加算したと考えられる.
となります。
2秒、256 MBメモリ
input :
n integers b1, b2, …, bn + 2, otherwise.
bから配列aが得られない場合は「-1」が出力され、そうでない場合は配列aが出力される.
some array a1, a2, …, an + 2 was guessed;
a配列が存在する.
array a was written to array b, i.e. bi=ai (1≤i≤n);
b配列にa配列が作成されました.
The (n+1)-th element of the array b is the sum of the numbers in the array a, i.e. bn + 2 = a1, a2, …, an;
bのn+1要素はa配列の和である.
The (n+2)-th element of the array b was written some number x (1≤x≤109), i.e. bn+2=x; The
bのn+2要素は任意のxである.
array b was shuffled.
b配列は混合されている.
bの最大値だから?あるいは,2番目に大きい値はa配列の和であるため,2回加算したと考えられる.
となります。
最大の値を和と見なすか、2番目を和と見なすことができます.
その結果,a配列要素を加算した値はbのn+1であるため,この値は大きくなることが分かった.そのため、2つの状況があります.
並べ替えの場合、一番後ろの値は和です.
または2番目の値.
x
したがって,−1に存在する最大値が和を表す場合,この値から2倍減算した値をxと見なすことができる.そしてこのxを取り除くと、私たちはaを得ることができます.
しかし、そうでなければ?
2番目の値は和とみなされるため、前に存在するすべての値が加算された値に等しくなければなりません.
どちらも気に入らない場合は-1を出力します.import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()
x = sum(data) - data[-1] * 2
if x in data[:len(data) - 1]:
data.remove(x)
print(*data[:n])
else:
if sum(data[:n]) == data[n]:
print(*data[:n])
else:
print(-1)
Reference
この問題について(D. Corrupted Array | Round #713 Div.3), 我々は、より多くの情報をここで見つけました
https://velog.io/@jsin2475/D.-Corrupted-Array-Round-713-Div.3
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
したがって,−1に存在する最大値が和を表す場合,この値から2倍減算した値をxと見なすことができる.そしてこのxを取り除くと、私たちはaを得ることができます.
しかし、そうでなければ?
2番目の値は和とみなされるため、前に存在するすべての値が加算された値に等しくなければなりません.
どちらも気に入らない場合は-1を出力します.
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()
x = sum(data) - data[-1] * 2
if x in data[:len(data) - 1]:
data.remove(x)
print(*data[:n])
else:
if sum(data[:n]) == data[n]:
print(*data[:n])
else:
print(-1)
Reference
この問題について(D. Corrupted Array | Round #713 Div.3), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/D.-Corrupted-Array-Round-713-Div.3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol