Keep the Customer Satisfied

题意：

n个订单，每个订单有完成需要的天数，和限制的天数，求最多能完成多少订单

分析：

先按限制日期升序排列，若当前订单不能完成，和上面已选中的订单中需要天数中最大的比较，若比它小，则替换他。

#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <complex> #include <cassert> #include <utility> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> PII; typedef long long ll; #define lson l,m,rt<<1 #define pi acos(-1.0) #define rson m+1,r,rt<<11 #define All 1,N,1 #define read freopen("in.txt", "r", stdin) const ll INFll = 0x3f3f3f3f3f3f3f3fLL; const int INF= 0x7ffffff; const int mod = 1000000007; struct node{int q,d; }a[800010]; int n; bool cmp(node x,node y){return x.d<y.d; } void solve(){sort(a,a+n,cmp);int sum=0,num=0;priority_queue<int>que;for(int i=0;i<n;++i){if(sum+a[i].q>a[i].d){if(que.empty())continue;int tmp=que.top();if(tmp>a[i].q){sum=sum+a[i].q-tmp;que.pop();que.push(a[i].q);}}else{num++;que.push(a[i].q);sum+=a[i].q;}}printf("%d\n",num); } int main() {int t,ca=0;scanf("%d",&t);while(t--){if(ca++)printf("\n");scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d%d",&a[i].q,&a[i].d);solve();} return 0; }

 

转载于:https://www.cnblogs.com/zsf123/p/4869951.html

总结

以上是生活随笔为你收集整理的Keep the Customer Satisfied的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。