[백준 8980] 택배

문제

https://www.acmicpc.net/problem/8980

 

알고리즘

Greedy

 

풀이

1부터 N까지 트럭이 이동하며 배송을 할 때, 최대 배송량을 구하는 문제입니다.

 

1마을에서 모든 택배를 들고 있을 때, 포기 해야하는 택배는 1마을로부터 가장 먼 택배들입니다. 이 택배는 오래 들고 있을수록 중간마을에서의 배송을 방해하기 때문입니다. 도착마을을 기준으로 오름차순으로 정렬하여 다른 택배들에게 영향을 덜 주는 순서대로 처리해나가면 풀 수 있습니다. 영향을 준다는 것은 현재 처리하고 있는 택배의 도착지가 다른 택배들의 시작점과 도착점 사이에 있다는 것인데 도착마을을 기준으로 오름차순 정렬하면 이와 같은 일이 최소화 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef tuple<int, int, int> tp;

int cap[2005];
int N, C, M;
vector<tp> info;
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> C >> M;
    rep(i, M) {
        int u, v, c;
        cin >> u >> v >> c;
        info.emplace_back(u, v, c);
    }
    int ans = 0;
    sort(info.begin(), info.end(), [](const tp& a, const tp& b) { return get<1>(a) < get<1>(b); });
    for (auto [u, v, c] : info) {
        int mx = *max_element(cap + u, cap + v);
        int plus = min(C - mx, c);
        ans += plus;
        for_each(cap + u, cap + v, [&](int& a) { a += plus; });
    }
    cout << ans;
    return 0;
}