[Codeforces Round 1004(Div.2)] B. Two Large Bags

https://codeforces.com/contest/2067/problem/B

Codeforces Round 1004(Div.2) - B. Two Large Bags

문제 유형: 투 포인터, 그리디, 정렬

시간 제한: 1초

메모리 제한: 256MB

 

문제

You have two large bags of numbers. Initially, the first bag contains n numbers: a1,a2,…,an, while the second bag is empty. You are allowed to perform the following operations:

• Choose any number from the first bag and move it to the second bag.
• Choose a number from the first bag that is also present in the second bag and increase it by one.

You can perform an unlimited number of operations of both types, in any order. Is it possible to make the contents of the first and second bags identical?

 

두개의 큰 가방이 있다.

첫 번째 가방에는 n개의 숫자가 들어있다: a1, a2, ..., an.

두 번째 가방은 비어있다.

다음의 두 가지 연산을 할 수 있다:

• 첫 번째 가방의 숫자를 하나 골라서 두 번째 가방에 옮기기
• 두 번째 가방에도 있는 숫자를 첫 번째 가방에서 골라서 1만큼 늘리기

연산을 얼마든지 적용해도 된다고 할 때, 첫 번째 가방을 두 번째 가방으로 만들 수 있을까?

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.

The first line of each test case contains an integer n (2≤n≤1000) — the length of the array a. It is guaranteed that n is an even number.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n).

It is guaranteed that the sum of n^2 over all test cases does not exceed 10^6.

 

테스트케이스의 개수 t가 첫째 줄에 주어진다.

테스트 케이스의 첫째 줄에는 정수 n이 있다. a배열의 길이이다. 짝수임이 보장되어있다.

테스트 케이스의 두 번째 줄에는 a1, a2, ..., an이 있다.

모든 테스트 케이스에서 n^2의 합이 10^6을 넘지않도록 보장된다.

 

출력

For each test case, print "YES" if it is possible to equalize the contents of the bags. Otherwise, output "NO".

You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

각 테스트케이스별로, 가능하면 "YES", 아니면 "NO"를 출력하시오. 대소문자 구분을 하지않습니다.

 

풀이

우선, 두 가방으로 분할하기 위해서는, 각 숫자별로 짝수개씩 만들어져야 한다.

 

핵심 전략은, 작은 숫자들부터 그리디하게 페어를 만들고, 나머지 중복숫자들은 다 다음 숫자로 올려버리는 것이다.

그리고 나머지 숫자들에서 또 똑같이 해주면 된다.

그렇게 최종적으로 모두 페어가 나오면, 성공인 것이다.

 

구현을 위해, 오름차순 정렬한다.

투 포인터를 이용해서, 현재 보는 가장 작은 숫자들의 페어가 만들어지면, 나머지는 모두 숫자를 높인다.

페어 제작에 성공하면, 그 페어의 한 쪽은 두 번째 가방으로 옮기면 나머지 페어에 포함되지 않는 같은 크기의 수들을 올릴 수 있다.

이를 배열의 끝까지 반복한다.

배열의 맨 마지막 숫자, 즉 가장 큰 숫자들의 개수가 짝수이면 가능한 것이고, 아니면 불가능하다.

또는, 중간에서 페어가 안만들어지면, 불가능하다.

 

[1, 1, 1, 1, 1, 1, 1, 4]의 예시를 보자.

첫 페어 [1, 1]이 만들어졌다. 1을 하나 옮겼다고 가정하고, 나머지 1들을 올릴 수 있다.

[1, 1, 2, 2, 2, 2, 2, 4]가 만들어졌다. 취소선은 두 번째 가방으로 옮긴 것으로 간주한다.

또 페어 [2, 2]가 만들어진다. 2를 하나 옮겼다고 가정하고, 나머지 2들을 3으로 올릴 수 있다.

[1, 1, 2, 2, 3, 3, 3, 4]가 만들어졌다.

또 페어 [3, 3]이 만들어졌다. 3을 하나 옮겼다고 가정하고, 나머지 3을 4로 올릴 수 있다.

[1, 1, 2, 2, 3, 3, 4, 4]가 만들어졌다.

페어 [4, 4]가 만들어졌다. 이제 남은 수는 없으니, [1, 1, 1, 1, 1, 1, 1, 4]는 "YES"이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> arr(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
  }

  sort(arr.begin() + 1, arr.end());

  int left = 1;
  int right = 2;
  bool flag = true;
  while (right <= n) {
    if (arr[left] != arr[right]) {
      flag = false;
      break;
    }
    right++;

    while (right <= n && arr[right] == arr[left]) {
      arr[right]++;
      right++;
    }

    if (right > n) {
      int len = right - left;
      if (len % 2 == 1) {
        flag = false;
      }
      break;
    }

    left += 2;
    right = left + 1;
  }

  if (flag) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}