우물 파기
문제
폴리매스 왕국의 사람들은 우물을 이용해 지하수를 마십니다.
지하수의 근원은 물의 돌이라고 알려져 있으나, 물의 돌의 정확한 위치를 알고 있는 사람은 아무도 없습니다.
최근 들어 인구가 늘어나자 물이 부족해졌습니다.<br. 사람들은 이를 해결하기 위해 두 개의 우물을 더 파려고 합니다.
우물을 팔 수 있는 곳은 N곳이 있으며, 이들 중에서 i번 위치와 j번 위치에 우물을 파면 Ai+Aj만큼의 이익을 얻을 수 있습니다.
우물을 파는 위치를 적당히 정해서 최대 이익을 얻는 것이 좋겠지만, 돌발 상황을 대비하여 모든 경우를 고려하려고 합니다.
당신의 목표는 가능한 모든 이익의 중간값을 찾는 것입니다.
즉, 우물을 팔 곳을 정하는 모든 S=n(n-1)/2가지 경우에 대해 얻을 수 있는 이익 중
⌈S/2⌉번째로 작은 것을 알아내려고 합니다. 이 문제를 해결하는 프로그램을 작성해 봅시다.
입력
첫 줄에는 우물을 팔 수 있는 위치의 수 N이 주어집니다.
둘째 줄에는 각 위치에 우물을 팠을 때 얻을 수 있는 이익을 나타내는 N개의 정수 A1, A2, ⋯, AN이 주어집니다.
출력
가능한 모든 이익 중 ⌈S/2⌉번째로 작은 값을 출력합니다.
제한
2 ≤ N ≤ 50000, 1 ≤ Ai ≤ 10^9
풀이
N이 50000개이므로 생기는 경우의 수는 N(N-1)/2니까 전부 구할 수는 없었다.
태그를 까보니 이분 탐색이라길래 어떻게 접근해야할까 하고 고민했다.
우선 중간값에 대해서 이분 탐색을 하려면 범위를 구해야 한다.
v가 정렬됐으면 가장 작은 값은 v[0]+v[1]이고, 가장 큰 값은 v[n-2]+v[n-1]이다.
문제를 YES/NO로 끝나는 문제로 변환을 해야지 이분 탐색으로 접근할 수 있다.
중간값을 구하는 문제는 배열에서 기준보다 작거나 같은 값이 (N(N-1)/2)/2개 이상인 값 중 최솟값이다.
이분 탐색으로 l = v[0]+v[1], r = v[n-2]+v[n-1]로 잡고 기준 gi = n*(n-1)/2로 놓는다.
이 때 mid보다 작거나 같은 값이 gi보다 적으면 l을 증가하고, gi보다 크거나 같으면 r을 감소한다.
그러면 mid보다 작거나 같은 값의 개수는 어떻게 구할 수 있을까?
이는 포인터 옮기기 방식으로 해결할 수 있다.
mid보다 작거나 같은 모든 합 v[i]+v[j]를 구할 때 i가 증가하면 j는 감소할 수 밖에 없다.
v는 이미 정렬된 상태이기에 v[i]가 증가하면 v[j]는 감소하기 때문이다.
그러면 j 자리를 point라는 변수로 놓고 n-1부터 시작한 다음, i를 반복문으로 돌리면서 v[i]+v[point]가
mid보다 작거나 같아지는 point를 더해주면 mid보다 작거나 같은 값의 개수를 구할 수 있다.
더할 때 v[2]+v[3], v[3]+v[2]같이 순서만 바꾼 값이 중복해서 더해지지 않도록 (point-i)만큼 더했고
그랬더니 point가 i보다 작아지는 경우가 생겨서 음수가 더해지지 않도록 조정했다.
이렇게 문제를 mid를 기준으로 조건에 맞는지 YES/NO로 대답하는 결정 문제로 바꿔 해결할 수 있었다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
bool flag=1;
cin >> n;
vector<long long> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
sort(v.begin(), v.end());
long long l = v[0]+v[1];
long long r = v[n-2]+v[n-1];
long long mid = (l+r) >> 1;
long long gi = n*(n-1)/2;
while(l+1<r){
mid = (l+r)>>1;
int cur = 0; // mid가 커질수록 cur이 커짐.
int point=n-1;
for(int i=0;i<n;i++){
while(point>i && mid <= v[i]+v[point]){
point--;
}
cur += max(0, (point-i)); //음수가 될 수 있나
}
if(cur<gi/2){
l = mid;
}
else r = mid;
}
cout << l;
return 0;
}