백준 2285 우체국

문제 링크
골드4치고는 어려운 문제..

우체국의 위치가 $k$일때 총 비용을 $C[k]$라고 하면 $C[k]$는 다음과 같습니다.

$C[k] = ∑_{i=1}^{k-1} (X[k] - X[i]) A[i] + ∑_{i=k+1}^{N} (X[i] - X[k]) A[i]$

$C[k]$의 그래프 유형을 파악하기 위해 $C[k+1]-C[k]$를 구하면

$C[k+1]-C[k] = (X[k+1] - X[k])(∑_{i=1}^{k-1} A[i] - ∑_{i=k+1}^{N} A[i])$

$D[k] = C[k+1]-C[k]$인 $D$를 가정한다고 했을 때

$X[k+1] - X[k] > 0$이므로 $D$는 $∑_{i=1}^{k-1} A[i] - ∑_{i=k+1}^{N} A[i]$의 부호에 따라서 부호가 결정됩니다.

D의 부호는 -이다가 특정 k이후 부터는 +가 됩니다.

즉, C의 그래프 개형은 감소하다가 증가한다.

저희는 어느순간부터 $C$가 증가하는지를 알아내야 합니다. 고로 $D$가 어느순간부터 0또는+가 되는지를 알아내야 합니다.
$∑_{i=1}^{k-1} A[i] - ∑_{i=k+1}^{N} A[i]$가 0보다 커지는 순간은 $∑_{i=1}^{k-1} A[i]$가 $∑_{i=1}^{N} A[i]$의 절반보다 크거나 같아지는 순간이므로 누적합이 전체과 같거나 커지는 순간을 구하는 문제로 바뀝니다.

#define ll long long

#include<bits/stdc++.h>

using namespace std;

struct Info{
    ll loc, sum;

    Info(ll loc, ll sum) : loc(loc), sum(sum){}

    bool operator<(Info a){
        return loc < a.loc;
    }
};

int N;
ll A[100'001]; // 위치
ll X[100'001]; // 사람 사는 수

vector<Info> v;

ll find(ll input){
    ll target = input%2==0?input/2 : input/2+1;
    ll sum = 0;
    for(int i = 0;i < N;i++){
        sum += v[i].sum;
        if(sum >= target) return v[i].loc;
    }
}

int main(){
    cin >> N;
    ll sum = 0;
    for(int i =1;i<=N;i++){
        cin >> A[i] >> X[i];
        v.push_back(Info(A[i], X[i]));
        sum += X[i];
    }
    // 위치 기반 정렬
    sort(v.begin(), v.end());

    //누적합
    cout << find(sum) << endl;

    return 0;
}