[백준 2513] 통학버스

• 문제 : 2513 통학버스

• 유형 : 그리디

• 아이디어 : 1461번 문제와 동일한 방식으로 접근하면 되는 문제였다. 학교를 기준으로 좌표가 음수인 구간과 양수인 구간을 나누어서 계산하고 음수 구간은 절대값이 가장 큰 지점부터 버스에 최대한 실으면서 이동 거리를 계산해주고 양수 구간도 똑같이 계산해주면 된다.

• 풀이 : 우선 학교 좌표와의 거리를 전부 구해주고 음수인 구간과 양수인 구간으로 나눈다. 음수인 구간은 최소힙을 사용해서 최대 k명까지 사람을 실어나르는 것을 반복하면서 거리를 계산하고 양수 구간에서는 최대힙에 좌표들을 넣고 똑같이 최대 k명까지 사람을 실어나르면서 거리를 계산한다.

• 코드

#include <bits/stdc++.h>	

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
	
int n, k, s;
pair<int, int > p[30001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> k >> s;
	for (int i = 0; i < n; i++) {
		cin >> p[i].first >> p[i].second;
	}
	p[n] = { s,0 };
	sort(p, p + n + 1);
	int T = lower_bound(p, p + n + 1, make_pair(s, 0)) - p;
	for (int i = 0; i < T; i++) pq.push({ p[i].first - s, p[i].second });

	int ans = 0;
	int t = k;
	int c = 0;
	while (!pq.empty()) {
		if(t == k)
			c += abs(pq.top().first);
		if (pq.top().second <= t) {
			t -= pq.top().second;
			pq.pop();
			if (t == 0) {
				ans += 2 * c;
				t = k;
				c = 0;
			}
		}
		else {
			auto temp = pq.top();
			temp.second -= t;
			t = k;
			pq.pop();
			pq.push(temp);
		}
	}
	ans += 2 * c;

	priority_queue<pair<int, int>> Q;
	for (int i = T + 1; i <= n; i++) Q.push({ p[i].first - s, p[i].second });
	t = k;
	c = 0;
	while (!Q.empty()) {
		if (t == k)
			c += abs(Q.top().first);
		if (Q.top().second <= t) {
			t -= Q.top().second;
			Q.pop();
			if (t == 0) {
				ans += 2 * c;
				t = k;
				c = 0;
			}
		}
		else {
			auto temp = Q.top();
			temp.second -= t;
			t = k;
			Q.pop();
			Q.push(temp);
		}
	}
	ans += 2 * c;

	cout << ans;
	return 0;
}