顾客是上帝 Keep the Customer Satisfied 题解

· · 题解

题目

题目传送门

思路

打眼一看，这道题要求最多能干多少工作，肯定是贪心。

知道这个就好做了，我们思考如何才能最优，我们将输入 开始时间和结束时间的数组 按照结束时间从小到大排列，显然是最优的。

定义一个变量 time 代表现在是什么时刻。

如果 time 加上起始时间比结束时间要小，就说明这个任务可以完成，time 加上开始时间，并将开始时间压入优先队列。

否则，在优先队列不空的前提下，我们选一个之前做过的任务用时最长的和现在的比较，如果现在的用时短，就把用时最长的扔掉，time 先减去用时最长的开始时间再加上现在的开始时间。将现在的开始时间压入优先队列。

最后输出优先队列里面有几项即可。

代码

#include<iostream>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
const int N=4e6+5;
const int INF=1e9;
struct customer{
    int st,fi;//start,finish
}c[N];
int n;
bool cmp(customer x,customer y){
    return x.fi<y.fi;
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        priority_queue<int> q;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>c[i].st>>c[i].fi;
        }
        int time=0;
        sort(c+1,c+1+n,cmp);
        for(int i=1;i<=n;i++){
            if(time+c[i].st<=c[i].fi){//如果时间加上起始时间比这个任务结束时间要早
                time+=(c[i].st);//时间加上任务的时间
                q.push(c[i].st);//进入优先队列
            }
            else{
                if(!q.empty()){
                    int d=q.top();
                    if(d>c[i].st){//如果这个任务比做过的任务中最大的用时要短
                        time-=d;
                        time+=c[i].st;//换掉任务，以求最优
                        q.pop();
                        q.push(c[i].st);
                    }
                }
            }
        }
        cout<<q.size()<<endl;
        if(T) cout<<endl;
    }

}
/*
 2
 6
 7 15
 8 20
 6 8
 4 9
 3 21
 5 22
 6
 7 15
 8 20
 6 8
 4 9
 3 21
 5 22
 */
/*
 2
 6
 7 15
 8 20
 6 8
 4 9
 3 21
 5 22
 6
 7 15
 8 20
 6 8
 4 9
 3 21
 5 22
 */

/*
 1
 6
 7 15
 8 20
 6 8
 4 9
 3 21
 5 22
 */