2141번 우체국

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

처음에는 거리(마을 사이의 거리), 마을 위치와 인원 수 모두 고려하려고 하였으나,

문제의 핵심은 인원 수였다.

우선 입력 받은 마을과 인원 수를 정렬 시킨 다음

차례대로 각 마을의 인원 수를 더해가면서,

그 합이 (전체 총 인원 수 + 1) / 2보다 크거나 같을 때의

마을의 위치를 출력해주면 된다.

어쨌든 가치(?)는 인원 수가 제일 중요하고,

인원 수가 많은 쪽에 되도록 우체국을 설치해야 하니,

중심(=(전체 총 인원 수 + 1) / 2)을 기준으로

계산한다.

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n;
    static long total = 0;
    static Vector<pair> v = new Vector<pair>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long a = Long.parseLong(st.nextToken());
            total += a;
            v.add(new pair(x, a));
        }
        
        Collections.sort(v, new Comparator<pair>() {
            public int compare(pair p1, pair p2) {
                if(p1.first < p2.first) {
                    return -1;
                }
                else if(p1.first == p2.first) {
                    if(p1.second < p2.second) {
                        return -1;
                    }
                }
                return 1;
            }
        });    
        
        long people = 0;
        
        for(pair p : v) {
            people += p.second;
            if(people >= (total + 1) / 2) {
                bw.write(String.valueOf(p.first) + "\n");
                break;
            }
        }
 
        bw.flush();
        bw.close();
    }
}
 
class pair{
    long first, second;
    pair(long f, long s) {
        this.first = f;
        this.second = s;
    }
}