COFO::1610C Keshi Is Throwing a Party

• Link : COFO::1610C

Problem

• level : 1600
• tag : binary search, greedy
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit : 20
• 해당 유형의 문제에서 선택될 갯수를 미리 fix하는건 상상하지 못했습니다.
• 단순한 인덱스 조작으로 오인했습니다.

Point

• n명의 사람이 주어집니다.
• i번째 사람은 i달러를 들고 있고 2개의 팩터를 보유합니다.
• a[i] : i번째 사람은 자신보다 돈이 많은 사람이 파티에 최대 a[i]명일때 파티에 참여합니다.
• b[i] : i번째 사람은 자신보다 돈이 없는 사람이 파티에 최대 b[i]명일때 파티에 참여합니다.
• 파티에 참여하는 사람의 최대 수를 구하시오.

Design

• 이 문제같은 유형에 binary search를 예상하지 못했습니다.
• bs 가 가능한 이유는 사람 수를 정했을때, 올 수 있는 사람의 수를 o(N) 내에 구할 수 있기 때문입니다.
• 이 로직이 매우 흥미롭습니다.
• 파티에 오는 사람의 리스트를 p1, p2, p3, … px 로 x명이라고 합시다.
  • 저는 이 리스트를 구하기 위해서 two pointer 처럼 풀어야하나? 라는 생각을 했습니다.
• O(N)내에 가능한 이유는 다음과 같습니다.
• p1 즉 돈이 제일 적은 사람의 a값은 x-1이상이어야하고, b값은 0이상이어야합니다.
  • 즉, p1보다 x-1명이 남았기 때문이죠.
• p2 즉, 돈이 두번째로 적은 사람의 a값은 x-2이상이어야하고, b값은 1이상이어야합니다.
  • 즉, p2보다 x-2명이 남았기 때문이죠.
  • 그리고, p2밑에는 1명이 있구요
• …
• 이 방법으로 O(N)내에 특정 인원수가 가능한지 여부를 체크할 수 있습니다.
• 간단해보이지만, 문제를 푸는 입장에서는 잘 보이지 않는 로직입니다.

Complexity

• O(NlogN)

Code

#include<bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define sz(a) (int) a.size()
#define rep(i, a, b) for(int i=(a); i <(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;

using namespace std;
const int MAXN = 2 * 1e5 + 9;

int n;
int a[MAXN], b[MAXN];

void bs(ll st, ll en) {
    
    auto possible = [](ll x) {
        ll cnt = 0;
        rep(i, 0, n) {
            if(a[i] >= x - 1 - cnt && b[i] >= cnt) cnt++;
        }
        return cnt >= x;
    };
    
    ll ans = 0;
    while(st <= en) {
        ll mid = (st + en) >> 1;
        if(possible(mid)) {
            ans = max(ans, mid);
            st = mid + 1;
        } else en = mid - 1;
    }
    cout << ans << '\n';
}
void solve() {
    cin >> n;
    rep(i, 0, n) cin >> a[i] >> b[i];
    
    bs(0, n);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}