2118 - 두 개의 탑

https://www.acmicpc.net/problem/2118

문제를 푸는 데 가장 크게 작용한 아이디어는

문제의 정답 $\le$ 전체 길이의 합 / 2

라는 사실이었다.

두 지점 사이의 거리는 "$x$ = [a, b) 사이의 부분 합" 라고 할 때 $x$ 와 전체 길이의 합 - $x$ 중 더 작은 것이 된다.
이러한 부분합들 중 가장 큰 것이 문제의 정답이다.

부분합을 구하려는 데 계속 $O(N^2)$ 밖에 안 떠올랐다. 시계방향과 반시계방향 두 경로 중 더 작은것을 선택하는 것 때문이었다.
"문제의 정답 $\le$ 전체 길이의 합 / 2" 이니까 전체 길이 합의 절반보다 작지만 가장 큰 수만 찾으면 되겠구나 생각하고 이진탐색을 궁리해보았다.

계산하고 하는 거리 [a, b) 는 a $\le$ b인 것들만 확인해도 충분했다. 예를 들어, [5, 3) 을 확인하고 싶다면 전체 거리의 합에서 [3, 4) 를 빼면 되기 때문이다. (한쪽 방향에 대해서만 본다면)

시계방향/반시계방향에 대해 위 계산을 범위를 좁혀가면서 했다.

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

#define INF 987654321

typedef long long lld;

int search(int a[], int n, const int& v){
    int l=0, r=n-1;
    while(l <= r){
        int m = (l+r)/2;
        if(a[m] == v) return a[m];
        else if(a[m] < v) l = m+1;
        else r = m-1;
    }
    return a[r];
}

int main(){
    int n;
    scanf("%d", &n);
    int a[50001];
    int sum[50001]={};
    for(int i=0; i<n; ++i){
        scanf("%d", &a[i]);
        sum[i+1] = sum[i];
        sum[i+1] += a[i];
    }
    
    int all = sum[n];
    int mid = all/2;
    
    int rev[50001]={};
    for(int i=0; i<n; ++i){
        rev[n-i] = all - sum[i];
    }
    
    int res = 0;
    for(int i=0; i<n; ++i){
        int part = search(sum+1+i, n-i, mid+sum[i])-sum[i];
        res = max(res, min(part, all-part));
    }
    
    for(int i=0; i<n; ++i){
        int part = search(rev, n-i, mid-sum[i])+sum[i];
        res = max(res, min(part, all-part));
    }
    
    printf("%d", res);
    
    return 0;
}