boj 2513 통학버스

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

 

학교(S)에서 출발하여 각 아파트 단지에 있는 모든 학생들을 버스로 태우고 들어와야 합니다.

버스에는 정원이 K명이라 같은 아파트 단지를 여러번 왔다가는 상황이 있습니다.

그렇다면 최대한 가까운 거리를 왔다갔다 하는 편이 더 이득이라고 볼 수 있습니다.

즉 최대한 멀리있는 학생부터 데려오도록 합니다.

 

우선 학생들의 위치는 학교 기준 좌, 우로 나눠져 있습니다.

그렇기 때문에 왼쪽에 있는 학생들 먼저 다 데려온 후 오른쪽 학생들을 다 데려오는 방식으로 접근할 수 있습니다. (반대도 상관 없습니다.)

 

idx는 현재 데려올 수 있는 학생들 중 가장 멀리있는 학생의 인덱스입니다.

왕복하여 데려오기 때문에 idx번째 학생과의 거리 * 2를 더해줍니다.

그 다음에 현재 위치의 학생들을 다 태웠다면 인덱스를 다음으로 옮겨줍니다.

반대쪽 학생들을 데려올때도 로직은 동일합니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 30001
using namespace std;
typedef pair<int, int> pii;
 
pii list[MAX];
int N, K, S;
 
void func() {
    sort(list, list + N);
 
    int idx = 0;
    int ret = 0;
    while (idx < N && list[idx].first < S) {
        ret += ((S - list[idx].first) << 1);
        int cnt = 0;
        while (idx < N && list[idx].first < S && cnt < K) {
            int tmp = min(K - cnt, list[idx].second);
            cnt += tmp;
            list[idx].second -= tmp;
            if (!list[idx].second) idx++;
        }
    }
 
    idx = N - 1;
    while (idx >= 0 && list[idx].first > S) {
        ret += ((list[idx].first - S) << 1);
        int cnt = 0;
        while (idx >= 0 && list[idx].first > S && cnt < K) {
            int tmp = min(K - cnt, list[idx].second);
            cnt += tmp;
            list[idx].second -= tmp;
            if (!list[idx].second) idx--;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> K >> S;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}