D. Corrupted Array | Round #713 Div.3
https://codeforces.com/contest/1512/problem/D
시간 2초, 메모리 256MB
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);
a 배열을 b 배열에다가 작성했습니다. -
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배열은 섞여졌습니다.
우리가 입력받은 값을 모두 더하는 경우 이 값은 2A + x가 됩니다. A는 배열 a의 합을 의미한다.
왜냐하면 b의 가장 큰 값? 혹은 두번째로 큰 값이 a 배열의 합이기에 두 번 더한 것으로 볼 수 있다.
합
가장 큰 값을 합으로 보거나 두 번째를 합으로 볼 수 있다.
결국 a 배열 원소 모두를 합한 값이 b의 n + 1번째 값이니까 이 값이 매우 클것이라는 것을 알 수 있다. 그렇기에 두 가지 경우가 존재한다.
정렬 했을 때 가장 뒤에 존재하는 값이 합이다.
또는 두 번째 값이다.
x
그래서 -1에 존재하는 가장 큰 값이 합을 나타낸다고 할 때 이 값의 2배를 뺀 값을 우리는 x로 볼 수 있다. 그리고 이 x를 제거해버리면 우리는 a를 얻을 수 있다.
근데 그렇지 않은 경우에는?
두 번째 값을 합으로 보기 때문에 그 앞에 존재하는 모든 값을 더한 값과 동일해야 한다.
이 두 가지를 모두 만족하지 않는 경우에는 -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)
Author And Source
이 문제에 관하여(D. Corrupted Array | Round #713 Div.3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/D.-Corrupted-Array-Round-713-Div.3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)