[BOJ 20982] 安全点検 (Safety Inspection)

Link

문제 링크

Problem

JOI시에는 1개의 충분히 긴 도로가 있습니다. 이 도로는 수직선으로 간주할 수 있으며, 각 지점은 1개의 실수에 의한 좌표로 표시됩니다. 또한 JOI시에는 이 도로를 따라 N개의 시설이 설치되어 있으며, 좌표가 작은 순서대로 1부터 N까지의 번호가 매겨져 있습니다. 시설 $i(1\le i\le n)$의 위치는 좌표 $A_i$입니다.

JOI 시에서는 이제 시설 안전 점검을 할 것입니다. 시설 i에는 점검해야 할 항목이 $B_i$개 있습니다. 이제 점검할 수 있는 K명의 목수가 모였습니다. 안전 점검이 시작될 때 목수는 모두 좌표를 0에 두고 있습니다. 점검이 시작되면 각 목수는 1분 동안 다음 두 가지 행동 중 하나를 취할 수 있습니다.

• 거리 1만큼 좌표를 이동합니다.
• 지금 있는 좌표에 있는 시설의 점검 항목 중 하나를 선택하여 점검합니다.

안전 점검을 마칠 때, 모든 건물의 모든 점검 항목이 한 명 이상의 목수에 의해 점검되어야 합니다.

목수의 인원과 시설에 대한 정보가 주어질 때, 안전 점검을 마치는데 최소 몇 분이 걸리는지를 요구하는 프로그램을 작성하세요.

Input

입력은 다음과 같은 형식으로 표준 입력으로부터 주어진다.

• $1\le N\le 100000$
• $1\le K\le {10}^9$
• $1\le A_i\le {10}^9$ $(1\le i\le N)$
• $A_i<A_{i+1}$ $(1\le i\le N-1)$
• $1\le B_i\le {10}^9$ $(1\le i\le N)$
• 입력되는 값은 모두 정수이다.

N K
A1 A2 … AN
B1 B2 … BN

Subtask

Index	Score	Restriction
1	3	K=1
2	15	K=2
3	82	No additional constraints.

Subtask 1($\mathcal{O}(1)?$)

한 사람이 다 해야하므로, 좌표로 이동하면서 그 좌표에 도착하면 일들을 다 하고, 다시 가고, 하고, 다시 가고, 하고… 를 하면 된다.

이는 단순 수학 계산으로 바꿀 수 있으므로, Input을 받으면서 다 처리해줄 수 있다. 따라서 복잡도는 $\mathcal{O}(1)$

Subtask 2($\mathcal{O}(N)$)

2명이서 일을 해 나가야하는데, 생각을 해보면 멀리 있는 일을 두명이 같이 하는 것은 비효율적임을 알 수 있다.

즉, 두 명 모두 일심동체가 되어 일 → 이동 → 일 → 이동을 반복하는 것보다, 한 사람은 가까운 부분들의 일만, 먼 사람은 먼 부분들의 일만 하는 식으로 진행을 한다.

두 번째 사람이 일을 하기 시작하는 시설물의 번호를 $x$라 하면, 위치 $A_{x-1}$까지는 1번 근무자가, $A_{x+1}$부터는 2번 근무자가 전체 시설점검을 하게 된다.

하지만, $A_x$번때 같은 경우 두 사람이 모두 일하게 되는데, 결국은 시간의 최소화가 목적이므로 시간에 맞게 최대한 공평하게 분배해주는 것이 좋다.

이를 종합하여 걸리는 시간에 대한 식을 써보면,

• $A_{x-1}$번째까지 이동하면서 모든 일을 처리하는 수: $A_x+\sum _{x<i}{B}_i$
• $A_{x+1}$부터 끝까지 이동하면서 모든 일을 처리하는 수: $A_N+\sum _{x>i}{B}_i$
• 최대한 공평하게 분배를 해주기 위해서는

$$A_x+\sum _{x<i}{B}_i+K=A_N+\sum _{x>i}{B}_i+(B_x-K)$$

을 만족하면 되므로, 이는 누적합을 통하여 $\mathcal{O}(1)$에 계산할 수 있다.

이후 끝나는 시간은 더 첫 번째 사람과 두 번째 사람 중 더 많은 시간을 쓰는 사람이다.

따라서 모든 가능한 $x$에 대해서 최솟값을 구하면 되므로, 복잡도는 $\mathcal{O}(N)$

Subtask 3($\mathcal{O}(Nlg(\sum B_i))$)

앞의 그리디 아이디어를 조금 발전시키자.

결국은 이동을 많이 한 사람이 뒤에 있는 일을 처리해야하는 것은 맞고, 이 사람들 위주로 시간이 계산이 되어야 하는 것이 맞다.

하지만, 앞에 같은 경우엔 2명이었기 때문에 식을 세우기 쉬웠지만, 지금은 $K$명이므로 쉽지 않다.

따라서, 생각을 다소 바꾸자.

시간 $T$일 때 만약 목수 $K$명으로 문제를 해결하는 것이 가능하다면, 그 이후의 시간에 대해서도 모두 해결이 가능하다.

이를 이용하여, 시간에 대한 이분탐색을 진행하는데, 말했다시피 목수 $K$명을 계산하는 것은 쉽지 않다.

그럼 목수에 대해서도 생각을 해보면, 만약 $3$명으로 일이 가능하다면 그보다 더 많은 목수은 $10$명을 데리고와도 일이 가능하다.

즉, 시간 $T$일 때 목수의 최솟값이 $K$명보다 작으면, 이는 $K$명의 목수로도 할 수 있음이 된다.

따라서, 우리는 시간 $T$가 주어졌을 때 안전 점검을 끝내려면 목수가 몇 명 최소 필요한지를 찾아서, 그 값이 $K$보다 작은지를 보면 된다.

이제 최솟값을 구하는 과정만이 남았는데, 목수가 적다는 뜻은 목수를 휴식시간 없이 최대한 많이 돌려야함을 의미한다.

즉, 이동 시간을 제외한 모든 시간에 목수들을 일하게 해야 한다.

만약 위치가 $A_i$이고 시간이 $T$, 안전점검 횟수가 $B_i$이면 $A_i$까지 오는데 소요되는 시간이 $T-A_i$이고 이 시간동안 모두 안전점검을 해야하므로 필요한 목수의 수는 $\lceil {\displaystyle \frac{T-A_i}{B_i}}\rceil$이다.

허나 올림 연산이므로 저렇게 할 경우 쉬는 목수가 생길 수 있는데, 이는 $A_{i-1}$번째 일을 할 때 모두 보내버리면 된다.

이렇게 계속 연산하여 필요 목수를 계산하면 된다. 자세한건 코드 참고

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a[100005],b[100005];
bool check(ll t){
    ll need=0,rest=0;
    for(int i=n-1;i>=0;i--){
        if(rest>=b[i]){
            rest-=b[i];
        }else{
            ll task=b[i]-rest;
            ll work=t-a[i];
            ll num=(task+work-1)/work;
            need+=num;
            rest=work*num-task;
        }
    }
    return need<=k;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    ll s=0;
    for(int i=0;i<n;i++){
        cin>>b[i];
        s+=b[i];
    }
    ll lo=a[n-1], hi=a[n-1]+s;
    while(hi-lo>1){
        ll m=(lo+hi)/2;
        if(check(m))hi=m;
        else lo=m;
    }
    cout<<hi<<endl;
}