통학버스 2513

문제

접근 방법

처음에는 좌우로 나뉜 이분 탐색인 줄 알았다. 하지만 그러기에는 거리를 기준으로 잡을 필요가 없기에 그리디라고 생각했다. (가장 먼 곳부터 갔다 오며 해결해야 이득이기 때문이다)
학교를 기준으로 좌우로 나누고 더 먼 곳의 우선순위가 높은 우선순위 큐를 사용하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue<pair<int, int>> rightPQ;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leftPQ;
    int N, K, S;
    cin >> N >> K >> S;
    while (N--)
    {
        pair<int, int> i;
        cin >> i.first >> i.second;
        if (i.first > S)
            rightPQ.push(i);
        else
            leftPQ.push(i);
    }
    int ret = 0, student = 0, topN;
    while (!rightPQ.empty())
    {
        auto cur = rightPQ.top();
        rightPQ.pop();
        if (student == 0)
            topN = cur.first;
        student += cur.second;
        if (student > K)
        {
            int dist = topN - S;
            student -= K;
            ret += (dist << 1);
            topN = cur.first;
            dist = topN - S;
            ret += ((student / K) * dist) << 1;
            student %= K;
        }
    }
    if (student > 0)
        ret += (topN - S) << 1;
    student = 0;
    while (!leftPQ.empty())
    {
        auto cur = leftPQ.top();
        leftPQ.pop();
        if (student == 0)
            topN = cur.first;
        student += cur.second;
        if (student > K)
        {
            int dist = S - topN;
            student -= K;
            ret += (dist << 1);
            topN = cur.first;
            dist = S - topN;
            ret += ((student / K) * dist) << 1;
            student %= K;
        }
    }
    if (student > 0)
        ret += (S - topN) << 1;
    cout << ret;
    return 0;
}

풀이

좌와 우로 나누어 입력받지만, 기본적인 동작은 같다.
더 먼 곳을 기준으로 학생을 태우고 학생 수가 기준을 넘으면 갱신해주면 된다.
학생 수를 더하는 과정에서 학생 수가 K의 배수만큼을 넘을 수도 있기에 같이 처리해주면 된다.
학생 수가 0이라는 것은 새 지점을 선택해야 한다는 뜻이므로 지점을 갱신해준다. 반복문이 끝난 뒤에도 남은 학생이 있을 수 있으니 계산해주면 된다.