习题 8-12 顾客是上帝（Keep the Customer Satisfied，ACM/ICPC SWERC 2005，UVa1153）

本文主要是介绍习题 8-12 顾客是上帝（Keep the Customer Satisfied，ACM/ICPC SWERC 2005，UVa1153），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1153
分类：贪心法
备注：不重叠区间变形

按截止时间从小到大排序，如果当前工作不能按时完成，则尝试替换之前选过工作中耗时最久的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=800000+5;
int t,n,kase;
struct node{int p,q;bool operator < (const node& b) const {return (q<b.q||(q==b.q&&p<b.p));}
}a[maxn];
int main(void){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&t);while(t--){if(kase++)printf("\n");scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d %d",&a[i].p,&a[i].q);sort(a,a+n);int pos=0;priority_queue<int>pq;for(int i=0;i<n;i++){if(pos+a[i].p<=a[i].q){pq.push(a[i].p);pos+=a[i].p;}else if(!pq.empty()){if(pq.top()>a[i].p&&pos+a[i].p-pq.top()<=a[i].q){pos+=a[i].p-pq.top();pq.pop(); pq.push(a[i].p);}}}printf("%d\n",pq.size());}return 0;
}

这篇关于习题 8-12 顾客是上帝（Keep the Customer Satisfied，ACM/ICPC SWERC 2005，UVa1153）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---