[백준/BOJ] 8980 택배

문제 : 8980번: 택배

그리디하게 접근하여

트럭이 가장 가까운곳에 배달할 수 있는

최대한의 택배를 실고 있다고 가정하고 풀면 된다.

문제의 조건에서는 박스를 받는 마을에서만 내릴 수 있지만,

그 마을에서 안실었다고 가정하여 배송한 택배수에서만 빼버리는 식으로

바꾸어 생각하면 쉽게 코드를 작성할 수 있다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct box{
    ll idx, val; //배송위치, 개수
    bool operator<(box& tmp){
        return idx<tmp.idx;
    }
};
ll N, C, M, ans, now;
vector<box> v[2005];
deque<box> dq;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> C >> M;
    while (M--){
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b,c});
    }
    for (int i=1;i<=N;i++){
        while (!dq.empty() && dq.front().idx==i){ //현재위치에서 배송할것이 있다면 배송
            now-=dq.front().val;
            ans+=dq.front().val;
            dq.pop_front();
        }
        sort(v[i].begin(),v[i].end()); //받는 위치가 가까운 순으로 정렬
        for (int j=0;j<v[i].size();j++){ //일단 모든 택배를 다실음
            dq.push_back(v[i][j]);
            now+=v[i][j].val;
        }
        sort(dq.begin(),dq.end()); //받는 위치가 가까운 순으로 정렬
        while (now>C){ //트럭 크기에서 넘치는 박스들을 버림
            ll x=dq.back().val;
            if (now-x>=C){
                dq.pop_back();
                now-=x;
            }
            else{
                dq.back().val-=now-C;
                now=C;
            }
        }
    }
    cout << ans;
    return 0;
}