백준 24913번 개표 - C++(cpp) 풀이

---

 

1. 1번 쿼리가 들어오면 정후를 제외한 후보자들의 득표수 합과 최대 득표수를 매 쿼리마다 업데이트한다.
2. 2번 쿼리가 들어오면 [y표를 더한 후의 득표수 합이 N*(X-1) 이하이면서, y표를 더하기 전 최고 득표수가 X 미만]인지 체크한다.

 

1. 1번 쿼리가 들어오면 정후를 제외한 후보자들의 득표수 합과 최대 득표수를 매 쿼리마다 업데이트한다.

 2번 쿼리를 수행하기 위해서는 정후를 제외한 후보자들의 득표수 합과 최대 득표수 정보가 필요하다. 1번 쿼리가 들어오면 이 두 값을 계산해두도록 한다.

 

2. 2번 쿼리가 들어오면 [y표를 더한 후의 득표수 합이 N*(X-1) 이하이면서, y표를 더하기 전 최고 득표수가 X 미만]인지 체크한다.

 정후를 제외한 후보자들의 득표수 합을 sum, 정후의 현재 득표수를 K라고 하자. 후보자의 N명의 득표수가 전부 K+x표 미만이 되도록 y개의 표를 분배해야 한다. 일단 y표를 분배하기 전 K+x표 이상을 득표한 후보자가 있다면 절대로 불가능하다. 그런 후보자가 없다면, sum+y 가 N*(K+x-1) 이하이면 전부 K+x표 이하가 되도록 분배할 수 있다. 총표수가 N*(K+x-1) 보다 크다면 누군가는 K+x 이상의 표를 가져야 하기 때문이다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

typedef long long ll;

const int MAX = 100002;
ll N, Q;
ll arr[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> Q;
    
    ll max_val = 0, sum = 0;
    
    ll t, x, y;
    for (int i=0; i<Q; i++) {
        cin >> t >> x >> y;
        
        if (t == 1) {
            arr[y] += x;
            
            if (y != N+1) {
                sum += x;
                max_val = max(max_val, arr[y]);
            }
        }
        else {
            ll hoo = arr[N+1] + x;
            if (max_val < hoo && sum+y <= N*(hoo-1)) cout << "YES\n";
            else cout << "NO\n";
        }
    }

    return 0;
}