建筑抢修(反悔贪心)

题目传送门

大致思路

声明一个建筑结构体: {$time$ 表示抢修需要的时间 , $limit$表示截止时间}
按截止时间升序排序,确保当前处理的一定是"最紧急"的:
注: $curr$ 示当前花费了多少时间
搞一个最大堆,表示当前计划抢修的建筑中,花费时间最长的
如果$time+curr≤limit$,直接入堆
否则,如果 $time$ 小于堆顶的花费时间,那么进行替换
这是一定不会超过 $limit$ 的 ,为什么?
前面处理的截止时间肯定不会比 $limit$ 宽松,但是却花费时间更多,这样替换, $curr$ 肯定不会超过 $limit$
最终堆的大小就为答案

Code

struct building {
    int time;
    int limit;
};

bool cmp (const building& b1, const building& b2) {
    return b1.limit < b2.limit;
}

void solve() {
    int n;
    cin >> n;
    vector<building> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].time>>v[i].limit;
    sort(v.begin(), v.end(), cmp);
    priority_queue<int> pq;
    int sum=v[0].time;
    int i=1;
    pq.push(v[0].time);
    while (!pq.empty() && i<n) {
        auto p = pq.top();
        if (sum+v[i].time <=v[i].limit && i<n) {
            pq.push(v[i].time);
            sum+=v[i].time;
        }
        else if (p >= v[i].time &&i<n) {
            sum-=p;
            pq.pop();
            pq.push(v[i].time);
            sum+=v[i].time;
        }
        i++;
    }
    cout<<pq.size()<<endl;
}