[BOJ]8980号:宅配便

質問リンク:白駿8980号です。
[質問へのアクセス]
dp問題かと思いましたがGRIDで答えられると思いGRIDで答えました.
最初は、最大容量で、できるだけ多くの容量を下げる方法で接近していました.つまり、村ごとの箱数を昇順に並べて最大容量にする方法です.
しかし、反例です.
1 4 40
2 3 10
3 4 40
もしそうなら、2->3->4のほうがいいです.
そこで他の方法で送信された村と受信した村が近いほど配送が多くなるので,受信した村を昇順に並べて送信した村->受信した村の間の村について箱計算を行った.
ex)
1 2 10
1 3 20
2 3 10
3 4 20
1 4 30
2 4 20
12、10日の時.
村
トラック:0+10/0/0/0
ans = 0 + 10 = 10
1 3 20日の時.
村
トラック:10+20/0+20/0
ans = 10 + 20 = 30
2 3 10日の時.
村
トラック:30/20+10/0/0
ans = 30 + 10 = 40
3 4 20日の時.
村
トラック:30/30/0+20/0
ans = 40 + 20 = 60
このようにして、村ごとに積むことができるトラックの容量数を計算した.
最大容量を超える場合は、トラックの容量の中で最大値の箱を各村に入れればよい.
1 4 30日時点で最大値が30なので入れる最大ケースは10です.
村
トラック:30+10/30+10/20+10/0
ans = 60 + 10 = 70
2 4 20時です.
村
トラック:40+0/40+0/30+0/0
ans = 70 + 0
ans=70が表示されます.
時間複雑度:O(M*logm)
[ソースコード]

#include <iostream>
#include <algorithm>

using namespace std;
int n,ts,m;
int ans;
typedef pair<pair<int, int>, int> p;

bool cmp(p a, p b) {
    return a.first.second < b.first.second;
}

int main() {
    cin >> n >> ts >> m;
    vector<p> arr;
    vector<int> truck(n);

    for(int i=0 ; i<m ; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        arr.push_back(p(make_pair(a, b), c));
    }
    sort(arr.begin(), arr.end(), cmp);
    
    int size = arr.size();
    for(int i=0 ; i<size ; i++) {
        int start = arr[i].first.first-1;
        int end = arr[i].first.second-1;
        int box = arr[i].second;
        int temp=0;
        int cnt=0;

        for(int j=start ; j<end ; j++) {
            temp = max(temp, truck[j]); // 해당하는 마을에서 쌓인 박스 수 중 가장 큰 수
        }
        if(temp+box<=ts) cnt = box; // 가장 큰 수에 박스를 넣어도 용량을 안넘으면
        else cnt = ts-temp; // 용량을 넘으면

        for(int j=start ; j<end ; j++) {
            truck[j] += cnt;
        }
        ans += cnt;
    }

    cout << ans << "\n";

    return 0;
}