ribari
(LLM 번역)
문제
작은 나라에 사람들이 주로 어부로 살고 있고, 모든 마을은 해안가 직선 도로 위에 위치해 있습니다.
마을 어부들은 엄청난 양의 물고기를 잡았지만,
예전처럼 물고기를 좋아하지 않아서 이웃 나라의 가난하고 굶주린 아이들을 입양하기로 했습니다.
해안가를 따라 하나의 긴 직선 도로가 모든 마을을 연결합니다.
따라서 각 마을(첫 번째와 마지막 마을 제외)은 양쪽 이웃 마을과 직접 연결되어 있습니다.
아이 한 명은 1년에 물고기 1톤을 먹습니다.
어떤 마을에서 잡은 물고기는 그 마을에서 먹을 수도 있고, 다른 마을로 운송할 수도 있습니다.
운송 중에는 도로 위의 세금 때문에 1킬로미터마다 물고기 1톤이 손실됩니다.
모든 마을이 같은 수의 아이를 입양받는 것을 조건으로, 각 마을에서 입양할 수 있는 아이의 최대 수를 구하는 프로그램을 작성하세요.
입력
첫 번째 줄에는 정수 N(1 ≤ N ≤ 100,000)이 주어져며, 이는 마을의 수입니다.
다음 N줄 각각에는 정수 A와 B가 주어집니다. A(1 ≤ A ≤ 1,000,000,000)는 마을의 위치,
B(0 ≤ B ≤ 1,000,000,000)는 마을의 연간 물고기 생산량을 의미합니다.
마을은 위치 기준 오름차순으로 정렬되어 있습니다.
참고: 주어진 테스트 데이터에서는 양수 해가 반드시 존재합니다.
출력
첫 번째 줄에 위 문제에서 구한 아이의 수를 출력합니다.
풀이
특정 구간에서 조건을 만족하는 최대 아이 수를 구해야 하기에 매개 변수 탐색으로 접근했다.
여기서 T/F를 판별할 때 식을 만드는 것이 헷갈렸는데 자신의 마을에 소비하고 남을 물고기는
어떤 마을로든 갈 수 있고, 양 방향으로 고려해야 한다.
또, 옮겼을 때 음수가 된다면 옮기는 것이 손해(불가능?)이므로 하면 안된다.
하지만 자신의 마을만 봤을 때 mid개 보다 적다면 다른 마을에서 물고기를 가져올 수 있는지 확인해야 한다.
이것들을 종합을 해보면 우선 자신의 마을에서 mid개를 빼고,
만약 양수라면 전이를 하는 것이 이득인지 아닌지 확인하며
음수라면 전이를 해서 빌려올 수 있는지 확인한 후, 마지막 마을에서 남은 물고기가 있는지 확인하는 식으로 해결했다.
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 0;
cin >> n;
vector<P> vp(n);
int mi=1e9+1, ma=-1;
for(int i=0;i<n;i++){
cin >> vp[i].first >> vp[i].second;
if(mi>vp[i].second)mi=vp[i].second;
if(ma<vp[i].second)ma=vp[i].second;
}
ll l=mi, r=ma;
while(l+1<r){
ll mid=(l+r)/2;
ans=0;
//cout << "mid: " << mid << '\n';
for(int i=0;i<n;i++){
ans+=vp[i].second;
ans-=mid;
if(i<n-1){
ll dst = vp[i+1].first-vp[i].first;
if(ans>=0 && ans<dst)ans=0;
else ans-=dst;
}
//cout << '!' << ans << '\n';
}
if(ans<0)r=mid;
else l=mid;
}
cout << l;
return 0;
}