택배를 마을에서 다른 마을로 보내는데 트럭 용량이 정해져있다.
최대한 많이 보낼 수 있는 택배양을 구하는 문제이다.
KOI 2013 초등부 3번문제인데 꽤나 어려웠다.
일단 "활동선택문제"와 같이 도착하는 마을이 작은 순서대로 정렬을 했다.
그 후에 마을을 1번부터 N번까지 가면서 최적값을 찾으려 했는데 구현하지 못하였다.
힌트를 보고 풀게되었는데 정렬을 한 후에 [s, e-1]까지 가능한 용량까지 채워넣으면 된다.
밑의코드는 구현 실패한 순차적으로 마을 이동하면서 답을 찾는 코드이다.
#include <cstdio>
#include <algorithm>
using namespace std;
struct Save { int l, r, c; };
int N, C, M;
Save save[10001];
int box[2001];
int main() {
scanf("%d%d%d", &N, &C, &M);
for (int m = 0;m < M;m++)
scanf("%d%d%d", &save[m].l, &save[m].r, &save[m].c);
sort(save, save + M, [](Save &a, Save &b)->bool {
if (a.r == b.r) {
if (a.l == b.l) return a.c > b.c;
return a.l < b.l;
}
return a.r < b.r;
});
int ans = 0;
for (int n = 0;n < M;n++) {
int mi = 0x3f3f3f3f;
for (int m = save[n].l; m < save[n].r;m++) mi = min(mi, min(C - box[m], save[n].c));
for (int m = save[n].l; m < save[n].r;m++) box[m] += mi;
ans += mi;
}
printf("%d\n", ans);
return 0;
}
| cs |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Save { int l, r, c; };
int N, C, M;
Save save[10001];
vector<pair<int, int>> v[2001];
int box[2001];
int main() {
scanf("%d%d%d", &N, &C, &M);
for (int m = 0;m < M;m++)
scanf("%d%d%d", &save[m].l, &save[m].r, &save[m].c);
sort(save, save + M, [](Save &a, Save &b)->bool {
if (a.r == b.r) {
if (a.l == b.l) return a.c > b.c;
return a.l < b.l;
}
return a.r < b.r;
});
for (int m = 0;m < M;m++) v[save[m].l].push_back({ save[m].r,save[m].c });
int ans = 0;
int cap = 0;
for (int n = 1;n <= N;n++) {
ans += box[n];
cap -= box[n];
box[n] = 0;
for (auto &m : v[n]) {
cap += m.second;
box[m.first] += m.second;
}
if (cap > C) {
for (int m = N; m >= n;m--) {
if (cap - box[m] <= C) {
int diff = cap - C;
cap -= diff;
box[m] -= diff;
break;
}
else {
cap -= box[m];
box[m] = 0;
}
}
}
}
printf("%d\n", ans);
return 0;
}
| cs |
현재 마을에서 일단 택배를 넣어주고 용량이 넘을 경우에 도착마을이 큰 곳에서부터 빼주면 된다.
댓글 없음:
댓글 쓰기