티스토리 뷰
Link
Problem
JOI시에는 1개의 충분히 긴 도로가 있습니다. 이 도로는 수직선으로 간주할 수 있으며, 각 지점은 1개의 실수에 의한 좌표로 표시됩니다. 또한 JOI시에는 이 도로를 따라 N개의 시설이 설치되어 있으며, 좌표가 작은 순서대로 1부터 N까지의 번호가 매겨져 있습니다. 시설 $i(1\leq i\leq n)$의 위치는 좌표 $A_i$입니다.
JOI 시에서는 이제 시설 안전 점검을 할 것입니다. 시설 i에는 점검해야 할 항목이 $B_i$개 있습니다. 이제 점검할 수 있는 K명의 목수가 모였습니다. 안전 점검이 시작될 때 목수는 모두 좌표를 0에 두고 있습니다. 점검이 시작되면 각 목수는 1분 동안 다음 두 가지 행동 중 하나를 취할 수 있습니다.
- 거리 1만큼 좌표를 이동합니다.
- 지금 있는 좌표에 있는 시설의 점검 항목 중 하나를 선택하여 점검합니다.
안전 점검을 마칠 때, 모든 건물의 모든 점검 항목이 한 명 이상의 목수에 의해 점검되어야 합니다.
목수의 인원과 시설에 대한 정보가 주어질 때, 안전 점검을 마치는데 최소 몇 분이 걸리는지를 요구하는 프로그램을 작성하세요.
Input
입력은 다음과 같은 형식으로 표준 입력으로부터 주어진다.
- $1\leq N \leq 100000$
- $1\leq K \leq 10^9$
- $1\leq A_i\leq 10^9$ $(1\leq i \leq N)$
- $A_i < A_{i+1}$ $(1\leq i \leq N-1)$
- $1\leq B_i \leq 10^9$ $(1\leq i \leq 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$이고 이 시간동안 모두 안전점검을 해야하므로 필요한 목수의 수는 $\left\lceil{}\dfrac{T-A_i}{B_i}\right\rceil{}$이다.
허나 올림 연산이므로 저렇게 할 경우 쉬는 목수가 생길 수 있는데, 이는 $A_{i-1}$번째 일을 할 때 모두 보내버리면 된다.
이렇게 계속 연산하여 필요 목수를 계산하면 된다. 자세한건 코드 참고
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#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;
}
|
cs |
'백준' 카테고리의 다른 글
[BOJ 20985] Snowball (0) | 2022.07.27 |
---|---|
[BOJ 16993] 연속합과 쿼리 (0) | 2022.07.23 |
[BOJ 17411] 가장 긴 증가하는 부분수열 6 (0) | 2022.07.21 |
[BOJ 2873] 롤러코스터 (0) | 2022.07.19 |
[BOJ 2843] 마블 (0) | 2022.07.18 |
- Total
- Today
- Yesterday
- 17411
- 세그먼트 트리
- Trace tirck
- 해석학 Chapter 5
- mathematics
- 로피탈
- PMA Ch5
- 연습문제
- Trace trick
- 해석학II
- Machine Learning
- 백준
- 수(상)
- icpc.me/17411
- LInear SVM
- Differentation
- 선형대수학
- PMA
- 백준 17411
- 해석학 Ch5
- Derivate
- 해석학
- 수학
- Deep learning
- 미분
- joi
- Backprop
- JOI 2021
- cs231n assignment1
- PMA 연습문제
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |