CSacademy Round #29 (Div. 2 only) D. Water Bottles

문제 링크

이 문제는 N개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,

물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 

이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.

이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이

적어도 하나는 있다고 가정한다.

일단 이 문제는 두가지의 풀이가 있다.

첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데

대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.

좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 막혀서 이 풀이로 오게된것인데 어쨌거나

라인 스위핑에서의 아이디어는 이 것이다. 우리가 현재 원하는 것이 N개의 물통에 물을 최대한 똑같이 채우는 것이다.

채워진 물의 양이 가장 많은 물통의 양을 high, 반대로 적은 물통의 양을 low 라고 하면 우리가 원하는 것은

high - low 가 최소로 하길 원하는 것이고, high - low 가 가장 최소가 될 때가 바로 모든 물통에 채워진 물의 양이

같을 때이기 때문이다. 그렇기 때문에 우리는 최대한 모든 물통의 양을 같은양으로 유지하면 채울 것이다.

이 점이 바로 그리디한 특성이다.

그런데 물론 여기서는 상한과 하한이라는게 있기 때문에 항상 모든 물통에 채우는 물의 양을 같게 할 수가 없다.

하지만 그래도 최대한 같은 양씩 동시에 넣어줄 것이다. 

그리고 각 물통에는 의무적으로 채워야 하는 양이 있다. 바로 하한인데, 이 하한이 존재하기 때문에

우리는 모두 빈물통에서부터 N개를 동시에 조금씩 채우는 식으로는 답을 구할 수가 없다. 그렇기 때문에

N개의 물통이 모두 비워져 있는 상태에서 물을 채우기 시작하는 것이 아니라, N개의 물통에 물을 일단

하한 만큼 다 채워놓고 시작을 할 것이다. 그러면 하한만큼 물을 일단 다 채웠으면 더 채워 넣어야 하는 물의 총량은

L - sum(s[i]) 일 것이다. (s[i] : i번째 물통의 하한, e[i] : i번째 물통의 상한) 그러면 아까 말했듯 우리는

N개의 물통의 양을 계속 최대한 같게 유지시키면서 동시에 같은양씩 나눠서 조금씩 채우고싶다. 그런데 현재

채워져 있는 물의 양이다르기 때문에(하한이 모두 다르기 때문에) 가장 물이 적게 들어있는 물통부터 채우기 시작하여

그 다음으로 물이 적게 들어있는 물통과 물의 양이 같을 때 까지 채워넣고 같아지면 이제는 두 물통을 같이 채우기 시작한다.

두 물통에 같은 양씩 동시에 채우기 시작하고 또 그 다음으로 물이 적게 들어있는 물통까지 채웠다면 이제는 또 세 물통에

물을 같이 채워넣기 시작하는 식이고 이 것을 계속 반복한다. 물을 다 채워넣을 수 있는 방법이 최소 한개는 있다고 했으므로

이말은 즉슨 sum(e[i]) 는 L 보다 작거나 같다는 뜻이 되기 때문에 언젠가는 앞으로 채워야 하는 물의 양인 L이 바닥날것이고

이 때 종료하여 가장 물이 적게 채워진 물통과 가장 물이 많이 채워진 물통의 물의 양의 차가 바로 답이 될 것이다.

그런데 여기서 문제가 있다. 바로 상한이다. 아까의 예에서 처음에 가장 물이 적게 채워져 있는 물통에 물을 채우다가

그 다음으로 물이 적게 채워져 있는 물통과 물의 양이 같아 지기전에 상한에 걸린다면 이 물통은 더이상 그만 채워야

할 것이다. 그럼 그냥 이 물통만 버리고 나머지 남은 물통에 대해서만 같은양씩 채워나가면 된다. 이게 최선이기 때문에

이건 어쩔 수 없다는 것을 직관적으로 알 수가 있다. 우리는 이미 최대한 모든 물통에 채워진 물의 양이 같도록

노력을 하고 있기 때문에 더이상 같게 할 수가 없는 것이다. 아무튼 이렇게 반복하다가 특정 물통이 상한에 걸렸을 경우엔

답을 갱신해 주면된다.

(어떤 물통을 더이상 채울 수 없게 되면 이것이 가장 적게 채워진 물통 즉 low일 가능성이 있기 때문이다.)

그리고 앞으로 채워야 하는 물의 양인 L이 다 떨어져서 종료하는 시점에 high(가장 많이 채워진 물통의 물 양)을

갱신해 주고 종료해야 할텐데, 이 때에는 현재 같이 채우고 있는 물통의 개수를 cnt 라고 하면

cnt 개의 물통은 L/cnt 만큼 채워지거나, (L+cnt-1)/cnt 만큼 채워지거나 둘중 하나일 것이다. 예를 들어

현재 물통 3개를 같이 채우고있었는데 앞으로 채워야 하는 물의 양이 4라면 1통은 2를 채우고 2통은 1을 채우게 될 것이다.

이 때 많이 채우는 (L+cnt-1)/cnt 를 채우고 난 값을 high 로 갱신하면 될것이다. 그리고 추가적으로 중간에 상한에 걸려서

버려지는 물통이 존재하지않았을 수도 있다. 이 때에는 low 가 아직 한번도 갱신되지 않은 상태이기 때문에 L/cnt 만큼

채운 뒤의 양으로 low를 갱신해준다.  코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N;
ll L;
ll lo[100003], hi[100003];
vector<pair<ll, ll> > v;
int main() {
    ll anshi=-infl, anslo=infl;
    scanf("%d%lld",&N,&L);
    for(int i = 0 ; i < N; i++){
        scanf("%lld%lld",&lo[i],&hi[i]);
        v.push_back({lo[i],1});
        v.push_back({hi[i],-1});
        L -= lo[i];
        anshi = max(anshi, lo[i]);
    }
    sort(v.begin(), v.end());
    ll cnt=0;
    ll prev = -1;
    for(int i = 0 ; i < v.size(); i++){
        ll pos = v[i].first;
        ll adder = v[i].second;
        if(prev != -1) {
            if(L <= (pos - prev) * cnt) {
                assert(cnt!=0);
                ll maxx = (L+cnt-1) / cnt;
                anshi = max(anshi, prev+maxx);
                anslo = min(anslo, prev+L/cnt);
                break;
            }
            else L -= (pos - prev) * cnt;
        }
        cnt += adder;
        prev = v[i].first;
        if(adder == -1) anslo = min(anslo, pos);
    }
    printf("%lld",anshi-anslo);
    return 0;
}
 

두번째 풀이 방법은 이분탐색(+그리디) 이다.

그런데 또 이분탐색으로 푸는 방법이 두가지가 있다. 하지만 기본적으로 위에서 설명했던 스위핑 풀이도

그렇고 모든 풀이가 최대한 N개의 물통에 채워주는 양을 같게 하는 방향으로 채워준다는 점에서

유사하다.

우리는 결과적으로 가장 적게 채워진 물통의 물 양인 low와 가장 많이 채워진 물통의 양인 high 가 있을 때

high - low 가 최소가 되는 답을 구할 것이다. 근데 조금만 생각해 보면

min(s[i]) <= low <= min(e[i])

max(s[i]) <= high <= max(e[i])

라는 사실을 알 수가 있다.

그리고 또 한가지 알 수 있는 사실이 low는 최대한 클 수록 좋다는 것이다.