8980 택배
풀이(그리디)
1
2
3
4
5
1. 각 도착지별로 정보를 따로 관리함.(같이해도 되긴함)
2. 도착지 1~N번까지 입력받은 C로 트럭 용량을 초기화함.
3. 도착지 2번부터 정보를 하나씩 뽑아가며 검사. 시작지점~현재 도착지-1 까지에서의 최소값을 뽑고, 그만큼을 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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, int>> list[2021];
int N, C, M, capacity[2021];
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
cin >> N >> C >> M;
for (int i = 0; i < M; i++) {
int a, b, c;
cin >> a >> b >> c;
list[b].push_back({ a,c });
}
for (int i = 1; i <= N; i++) {
capacity[i] = C;
sort(list[i].begin(), list[i].end());
}
int shipped = 0;
for (int i = 2; i <= N; i++) {
for (int j = list[i].size() - 1; j >= 0; j--) {
int s = list[i][j].first, box = list[i][j].second, m = 2000000000;
for (int k = s; k < i; k++) {
m = min(m, capacity[k]);
}
int howMany = min(box, m);
for (int k = s; k < i; k++)
capacity[k] -= howMany;
shipped += howMany;
}
}
cout<< shipped;
}