[그리디] 백준 8980 택배 C++

 

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

8980번: 택배

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Info {
    int start, end, cnt;
};

bool operator < (const Info &a, const Info &b) {
    if (a.end != b.end) return a.end < b.end; // 도착 번호 오름차순
    else if (a.start != b.start) return a.start < b.start;
    else return a.cnt < b.cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, c, m;
    cin >> n >> c >> m;

    vector<Info> v(m, {0, 0, 0});
    for(int i=0; i<m; i++) {
        cin >> v[i].start >> v[i].end >> v[i].cnt;
        v[i].start--; v[i].end--;
    }
    sort(v.begin(), v.end(), less<>());

    vector<int> box(n, 0);
    int answer = 0;
    for(int i=0; i<m; i++) {
        Info now = v[i];
        
        int cnt = 0;
        for(int j=now.start; j<now.end; j++) cnt = max(cnt, box[j]); // j일 때, 트럭 안 박스 개수
        int load = min(now.cnt, c - cnt); // 트럭 안 여유 개수
        
        for(int j=now.start; j<now.end; j++) box[j] += load; // 트럭에 넣기
        answer += load;
    }

    cout << answer;

    return 0;
}

// 실패
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Info {
    int start, end, cnt;
};

bool operator > (const Info &a, const Info &b) {
    if (a.end != b.end) return a.end > b.end;
    else if (a.start != b.start) return a.start > b.start;
    else return a.cnt > b.cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, c, m;
    cin >> n >> c >> m;

    priority_queue<Info, vector<Info>, greater<>> v;
    int start, end, cnt;
    for(int i=0; i<m; i++) {
        cin >> start >> end >> cnt;
        v.push({start, end, cnt});
    }

    priority_queue<Info, vector<Info>, greater<>> truck;

    int answer = 0;
    int box = 0;
    for(int i=1; i<=m; i++) {
        while(!truck.empty()) { // 하차
            Info now = truck.top();
            if (now.end != i) break;
            truck.pop();
            
            box -= now.cnt;
            answer += now.cnt;
        }

        while(!v.empty()) { // 상차
            Info now = v.top();
            
            if (now.start != i) break;
            v.pop();
            
            if (box >= c) break;
            int load = (c - box > now.cnt)? now.cnt : c - box;
            
            box += load;
            truck.push({now.start, now.end, load});
        }
    }

    cout << answer;

    return 0;
}