BOJ 11982 : Angry Cows (Gold)

알고리즘

dp, two_pointer

시간복잡도

$O(NlogN)$

풀이

현재 점 왼쪽의 모든 점을 연쇄적으로 터뜨릴 수 있는 최솟값을 $dpl[i]$,
마찬가지로 오른쪽의 경우 $dpr[j]$로 구한다.

 

임의의 두 점에 대하여 두 점 사이 거리의 절반,
앞에서 구한 $dpl, dpr$ 값들 중 최댓값이 전체 최솟값 후보일 것이다.
이를 $O(N^2)$로 구하면 시간초과가 나기에
맨 끝에서부터 two pointer로 관리해주면 된다.
(dp값이 작은 것을 밀도록)

코드

#include <bits/stdc++.h>
using namespace std;

int N, a[50005], dpl[50005], dpr[50005];
int ans = 2e9;

int main()
{
    cin>>N; for (int i = 1; i <= N; i++) {cin>>a[i]; a[i]*=2;}
    sort(a+1, a+N+1);
    dpl[1] = dpr[N] = -2;
    dpl[2] = a[2] - a[1]; dpr[N-1] = a[N] - a[N-1];
    int len = 0, now = dpl[2] + 2;
    for (int i = 3; i <= N; i++) {
        len += a[i] - a[i-1];
        if (len <= now) {dpl[i] = now; continue;}
        dpl[i] = max(dpl[i-1] + 2, a[i] - a[i-1]);
        now = dpl[i]; len = a[i] - a[i-1];
    }
    len = 0; now = dpr[N-2] + 2;
    for (int i = N-2; i >= 0; i--) {
        len += a[i+1] - a[i];
        if (len <= now) {dpr[i] = now; continue;}
        dpr[i] = max(dpr[i+1] + 2, a[i+1] - a[i]);
        now = dpr[i]; len = a[i+1] - a[i];
    }
    int i = 1, j = N;
    while (i < j)
    {
        ans = min(ans, max((a[j]-a[i])/2, max(dpl[i]+2, dpr[j]+2)));
        dpl[i+1] < dpr[j-1] ? i++ : j--;
    }
    if (ans%2) cout<<ans/2<<".5";
    else cout<<ans/2<<".0";
    return 0;
}