E2-F

题目要求

核心算法和原理

代码

#include <bits/stdc++.h>
using namespace std;
int m, n, tl;
struct task{
    int t;  //start time
    int s;  //span
    int w;
}a[200002];
struct cpu{
    friend bool operator< (cpu c1, cpu c2){ //small root heap, < -> >
        if(c1.r == c2.r){
            return c1.idx > c2.idx;
        }
        return c1.r > c2.r;
    }
    int idx;
    int r;  //finish time

    cpu(int _idx): idx(_idx), r(0){}
};

long long ans[200002];


int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i].t >> a[i].w >> a[i].s;
    }

    priority_queue<cpu> qb, qe; //busy and empty
    for(int i = 1; i <= n; i++){
        qe.push(cpu(i));
    }

    for(int i = 0; i < m; i++){
        tl = a[i].t;
        while(!qb.empty()){
            cpu c = qb.top();
            if(c.r <= tl){
                c.r = 0;
                qe.push(c);
                qb.pop();
            }else{
                break;
            }
        }

        if(!qe.empty()) {
            cpu cn = qe.top();
            cn.r = a[i].t + a[i].s;
            ans[cn.idx] += a[i].w;
            qe.pop();
            qb.push(cn);
        }
    }

    for(int i = 1; i <= n; i++){
        cout << ans[i] << endl;
    }
    return 0;
}