백준 33152 (C++) 경인 국가의 행사

최초 업로드: 2025-10-13 19:59:33

최근 수정 시간: 2025-10-13 19:59:33

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 경인 국가의 행사

[문제 링크](https://www.acmicpc.net/problem/33152)

## 문제 설명

2024년, shake! 나라가 건국되었다. 건국을 맞아 shake! 나라는 초대 대통령을 선출하고자 하며, $X$ 후보와 $Y$ 후보, 총 $2$명의 후보가 당선을 놓고 경쟁하게 된다. shake! 나라는 총 $N$개의 도시로 이루어져 있으며 $i$번 도시에는 $A_{i}(1\leq i \leq N)$명의 국민들이 거주하고 있다. 민주주의 국가인 shake! 나라는 대통령을 뽑기 위한 선거 방식을 고민하던 중, 수연이와 현빈이가 각자 아이디어를 내게 되었다.

<ol>
	<li>수연이의 방식
	<ul>
		<li>shake! 나라의 국민들이 투표를 진행하고, 각 국민들이 거주하는 도시와 관계 없이 표를 합산한다.</li>
		<li>최종적으로 더 많은 표를 얻은 후보가 당선된다.</li>
	</ul>
	</li>
	<li>현빈이의 방식
	<ul>
		<li>shake! 나라의 국민들이 투표를 진행하고, 각 국민들의 표는 국민들이 거주하는 도시의 표에 합계된다. </li>
		<li>각 도시마다 더 많은 표를 얻은 후보가 해당 도시에서 승리한다.</li>
		<li>최종적으로 더 많은 도시에서 승리한 후보가 당선된다.</li>
	</ul>
	</li>
</ol>

예를 들어, $3$개의 도시에 각각 $801$명, $556$명, $500$명이 살고 있고, 투표 결과가 아래와 같다고 해보자.

만약 선거를 수연이의 방식으로 진행하게 된다면 $X$ 후보는 $650+100+180=930$표, $Y$ 후보는 $151+456+320=927$표를 받아 $X$ 후보가 당선된다. 반면 현빈이의 방식으로 선거를 진행하게 되면, $X$ 후보는 $1$번 도시에서만 승리하고, $Y$ 후보는 $2$, $3$번 도시에서 승리하여 $Y$ 후보가 당선된다.

모든 국민이 투표에 참여하며 하나의 후보에게만 투표를 할 수 있을 때 선거 진행을 수연이의 방식으로 하면 $X$ 후보가, 현빈이의 방식으로 하면 $Y$ 후보가 승리하는 경우를 찾아보자. 단, 투표가 동률이라면 두 후보 모두 패배한 것으로 생각한다.

## 입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.$(1\leq T\leq 100\,000)$

다음 줄부터 각 테스트 케이스의 정보가 주어진다. 하나의 테스트 케이스는 두 개의 줄로 이루어져 있으며, 첫 번째 줄에 shake! 나라의 도시 수 $N$이 주어진다. $\left(1\leq N \leq 10^{6}\right)$

두 번째 줄에 각 도시에 사는 국민의 수를 나타내는 정수 $A_{1},A_{2},\dots,A_{N}$이 공백으로 구분되어 주어진다. $(1\leq A_{i}\leq 10^{9})$

모든 테스트 케이스의 $N$의 합은 $10^6$을 넘지 않는다.

## 출력

각 테스트 케이스마다 shake! 나라의 선거 진행을 수연이의 방식으로하면 $X$ 후보가, 현빈이의 방식으로하면 $Y$ 후보가 승리하는 경우가 존재한다면, 첫 번째 줄에 <code>YES</code>를 출력하고 두 번째 줄에 $1$번부터 $N$번 도시까지 $X$ 후보가 얻은 표의 수를, 세 번째 줄에 $Y$ 후보가 얻은 표의 수를 공백으로 구분하여 출력한다.

그렇지 않다면 첫 번째 줄에 <code>NO</code>를 출력한다.

가능한 경우가 여러 개라면, 그중 아무거나 출력한다.

## 풀이
내림차순으로 정렬한 후 왼쪽 (n-1)/2개는 X에게 전부 주고, 나머지는 홀수일 때 1 차이나게 짝수일 때 2 차이나게 배분한다. 여기서 만약 n이 홀수인 경우, 왼쪽 m개 오른쪽 m+2개여서 짝수인 것이 존재하면 하나는 차이를 0으로 만드는 것이 최적이다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;

int res[1'000'000][2];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 int n; cin >> n;
 vector v;
 for(int i=0;i<n;i++) {
 int a; cin >> a;
 v.push_back({a, i});
 }
 sort(v.begin(), v.end(), greater());

long long sum=0;
 for(int i=0;i<(n-1)/2;i++) {
 sum += v[i].first;
 res[v[i].second][0] = v[i].first;
 res[v[i].second][1] = 0;
 }

bool equal = n%2==0;
 for(int i=(n-1)/2;i<n;i++) {
 if(equal && v[i].first%2==0) {
 res[v[i].second][0] = res[v[i].second][1] = v[i].first/2;
 equal=false;
 } else {
 res[v[i].second][0] = (v[i].first-1)/2;
 res[v[i].second][1] = v[i].first - (v[i].first-1)/2;
 sum += res[v[i].second][0] - res[v[i].second][1];
 }
 }
 if(sum>0) {
 cout << "YES\n";
 for(int i=0;i<2;i++) {
 for(int j=0;j<n;j++) cout << res[j][i] << ' ';
 cout << '\n';
 }
 } else {
 cout << "NO\n";
 }
 }
}
```