题解：UVA1153 顾客是上帝 Keep the Customer Satisfied

· · 题解

一车经验。

收集方式为以各题讨论区的双倍经验为出边边集进行 bfs，笔者未经检验不保证不包含诈骗。修缮题单请联系我。

每个任务有一个截止时间，于是有贪心思路，让截止时间急的优先完成。

但这是错的，有一个完不成了，那么无论如何都会少一个任务，于是不一定舍弃当前任务，可以贪心的找一个前面很长的任务扔掉节约时间。

于是套一个优先队列，做完了。

方案把优先队列里面的按原顺序排回去，然后统计开始时间就行。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fish{
    int fix,ed;
    bool operator <(const fish &x)const{
        return fix<x.fix;
    }
    int id,st;
}a[1500005];
bool cmp(fish x,fish y){
    return x.ed<y.ed;
}
void solve(){
    priority_queue<fish>q;
    int sum=0;
    vector<fish>ans;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].fix>>a[i].ed,a[i].id=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        a[i].st=sum+1;
        sum+=a[i].fix;
        q.push(a[i]);
        while(sum>a[i].ed)
        sum-=q.top().fix,q.pop();
    }
    cout<<q.size()<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
        if(t)cout<<'\n';
    }
    return 0;
}
// 这种几乎要刺痛双眼的奢华装潢，是源自于豚头族【Ork】的特有习性。
// 他们的寿命很有限，对于一切财产并不会抱持「哪一天可能会用到」的想法。
// 他们会让手上的所有财产在任何一瞬间都闪耀发光。
// 有时候是一种比喻，有时候是物理上的意思。