[백준] 14792 14793 14794 - Bathroom Stalls (c++)

https://www.acmicpc.net/problem/14794

 

문제 요약

화장실에 N+2개의 칸이 있다. 양 끝 칸엔 처음 부터 사람이 있고 K명의 사람들이 순차적으로 칸에 들어갈 것이다.

각 사람이 들어갈 화장실 칸은 다음과 같이 구할 수 있다.

 

• 각 빈 칸 S에 대해 LS와 RS라는 값을 계산한다. LS는 칸 S에서 왼쪽으로 가장 가까운 사용 중인 칸까지의 거리이고, RS는 S에서 오른쪽으로 가장 가까운 사용 중인 칸까지의 거리이다.
• 모든 빈 칸 S 중에서 min(LS, RS) 값이 최대인 칸들을 선택한다.
• 만약 여러 칸이 있다면, 이들 중에서 max(LS, RS) 값이 최대인 칸을 선택한다.
• 여전히 여러 칸이 남아 있다면, 가장 왼쪽에 있는 칸을 선택한다.

마지막 사람이 들어가는 칸의 max(LS,RS)와 min(LS,RS)를 구해라.

 

 

풀이 (KlogN)

• 트리 셋

LS와 RS 값만 묻는다는게 중요한 포인트이다. 어느칸에 들어가는지 알 필요가 없다는 뜻이다.

화장실 빈칸을 구간으로 나타냈을 때, min(LS,RS)가 최대인 곳이란 그냥 가장 큰 구간 가운데 들어가는 것이고 다른 세세한 조건은 신경 쓸 필요가 없다. 구간 크기에 대해 구간이 몇개 있는지를 map으로 저장하고 가장 큰 구간 크기를 선택해서 반으로 쪼개주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin >> t;
    int tc = 1;
    while(t--) {
        ll n,k;cin>>n>>k;
        map<ll,ll> cnt;
        cnt[n]++;
        ll l,r;
        while(k>0) {
            auto it=prev(cnt.end());
            ll len=it->first,c=it->second;
            cnt.erase(it);
            l=len-1>>1;r=len/2;
            cnt[l]+=c;
            cnt[r]+=c;
            k-=c;
        }
        cout<<"Case #"<<tc++<<": "<<max(l,r)<<' '<<min(l,r)<<'\n';
    }
}