[Codeforces Round 996(Div.2)] - B. Crafting

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

Codeforces Round 996(Div.2) - B. Crafting

문제 유형: 수학, 그리디

시간 제한: 1초

메모리 제한: 256MB

 

문제

There are n different types of magical materials, numbered from 1 to n. Initially, you have ai units of material i for each i from 1 to n. You are allowed to perform the following operation:

• Select a material i (where 1≤i≤n). Then, spend 1 unit of every other material j (in other words, j≠i) to gain 1 unit of material i. More formally, after selecting material i, update array a as follows: ai:=ai+1, and aj:=aj−1 for all j where j≠i and 1≤j≤n. Note that all aj must remain non-negative, i.e. you cannot spend resources you do not have.

You are trying to craft an artifact using these materials. To successfully craft the artifact, you must have at least bi

units of material i for each i from 1 to n.

Determine if it is possible to craft the artifact by performing the operation any number of times (including zero).

 

n개의 서로 다른 마법의 물질들이 있습니다. 1~n까지 번호가 붙어있습니다.

i번 물질에 대해 a_i개 가지고 있습니다.

당신은 이 연산을 0번 이상 할 수 있습니다:

•  물질 i(1 <= i <= n)을 골라서, i!=j이고 1<= j <= n인 물질들 j에 대해 개수 a_j를 1씩 낮추고, a_i를 1 올리기. 대신, 모든 a_j가 양수일때만 가능합니다.

i물질로 물건을 만들려면, b_i개만큼 소모해야 합니다.

물건을 만들 수 있는지 알아내시오.

 

입력

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 a single integer n (2≤n≤2⋅10^5) — the number of types of materials.

The second line of each test case contains n integers a1,a2,…,an (0≤ai≤10^9) — the amount of each material i that you currently hold.

The third line of each test case contains n integers b1,b2,…,bn (0≤bi≤10^9) — the amount of each material i needed to produce the artifact.

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

 

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

각 테스트케이스의 첫 줄에는 물질의 개수 n이 주어진다.

각 테스트케이스의 두 번째 줄에는 현재 물질의 개수 a배열이 공백으로 구분되어 주어진다.

각 테스트케이스의 세 번째 줄에는 만드는데 필요한 개수 b배열이 공백으로 구분되어 주어진다.

 

출력

For each test case, print a single line containing either "YES" or "NO", representing whether or not the artifact can be crafted.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

 

각 테스트케이스별로, 가능한지 여부를 "YES"또는 "NO"로 출력하시오. 

대소문자의 구분은 필요없습니다.

 

풀이

일일이 구현하면서 체크하기에는 너무 느리다.

대신, 스마트하게 판단하는 방법이 있다.

a[i] = a[i] - b[i] (for i in range 0 ~ n)을 적용해준다.

a[i]가 음수면 그만큼 부족하다는 의미, 0이면 정확히 충족된다는 의미, 양수면 여유분이 있다는 이미이다.

 

핵심은 음수인게 둘 이상이면 안되고, 음수가 충족되는 요소의 최소 여유분보다 작아야 한다는 것이다.

음수에서 음수로 양보하면 답으로 수렴할 수 없다.

순차적으로 a[i]를 순회하면서 음수면 부족한 물질의 카운트를 누적하면서 가장 작은 음수를 저장하고, 0 이상이면 최소 여유분을 업데이트한다.

 

최종적으로 음수카운트가 2 이상이거나 가장 작은 음수가 최소여유분보다 절대값이 크면 불가능하고, 이외의 경우에는 가능하다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);

  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int temp;
  int minimum_lack = 0;
  int minimum_satisfied = INT_MAX;
  int lack_count = 0;
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    a[i] -= temp;
    if (a[i] >= 0) {
      minimum_satisfied = min(minimum_satisfied, a[i]);
    } else {
      lack_count++;
      minimum_lack = min(minimum_lack, a[i]);
    }
  }

  if (lack_count >= 2 || abs(minimum_lack) > minimum_satisfied)
    cout << "NO\n";
  else
    cout << "YES\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}