傻逼题不会系列

Problem

给 n 个需要 t 时间完成的工作
每个工作必须要在 ei 时间前完成
问最多能完成多少个工作

多组数据
输出中每组数据之间有一个空行（？？）

Solution

被 shabi 输出坑了挺久
然而并不会这道题

对于现在的方案，如果要加入一个工作但没法加入，有三种操作可选：

1. 交换完成工作序列
2. 替代一个工作
3. 放弃这个工作

如果我们给加入时间排个序，那么第一个操作就可以免了，因为无论怎么交换都无法加入这个工作
所以只剩替代一个工作或者放弃。
当然是替代所耗时间最长的工作。
后方的所有工作都会左移，因此保证合法。
放弃不讲。
然后就没啦？

// Code by ajcxsu
// Problem: keep the customer satisfied

#include<bits/stdc++.h>
using namespace std;

const int N=8e5+10;
struct Order {
    int t, e;
} o[N];
bool cmp(const Order &a, const Order &b) { return a.e<b.e; }

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--) {
        int tot=0, n;
        cin>>n;
        for(int i=0;i<n;i++) cin>>o[i].t>>o[i].e;
        sort(o, o+n, cmp);
        priority_queue<int> pq;
        for(int i=0;i<n;i++) {
            if(tot+o[i].t>o[i].e) {
                if(pq.empty() || o[i].t>=pq.top()) continue;
                tot-=pq.top(), pq.pop(), pq.push(o[i].t), tot+=o[i].t;
            }
            else tot+=o[i].t, pq.push(o[i].t);
        }
        cout<<pq.size()<<endl;
        if(t) cout<<endl; // surprise mother fxxker
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uva-1153.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆