https://www.acmicpc.net/problem/2513
학교(S)에서 출발하여 각 아파트 단지에 있는 모든 학생들을 버스로 태우고 들어와야 합니다.
버스에는 정원이 K명이라 같은 아파트 단지를 여러번 왔다가는 상황이 있습니다.
그렇다면 최대한 가까운 거리를 왔다갔다 하는 편이 더 이득이라고 볼 수 있습니다.
즉 최대한 멀리있는 학생부터 데려오도록 합니다.
우선 학생들의 위치는 학교 기준 좌, 우로 나눠져 있습니다.
그렇기 때문에 왼쪽에 있는 학생들 먼저 다 데려온 후 오른쪽 학생들을 다 데려오는 방식으로 접근할 수 있습니다. (반대도 상관 없습니다.)
idx는 현재 데려올 수 있는 학생들 중 가장 멀리있는 학생의 인덱스입니다.
왕복하여 데려오기 때문에 idx번째 학생과의 거리 * 2를 더해줍니다.
그 다음에 현재 위치의 학생들을 다 태웠다면 인덱스를 다음으로 옮겨줍니다.
반대쪽 학생들을 데려올때도 로직은 동일합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#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;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 15553 난로 (0) | 2024.07.13 |
|---|---|
| boj 1437 수 분해 (0) | 2024.07.12 |
| boj 23559 밥 (0) | 2024.07.11 |
| boj 2140 지뢰찾기 (0) | 2024.07.10 |
| boj 1132 합 (0) | 2024.07.08 |