本文共 824 字,大约阅读时间需要 2 分钟。
和 一模一样,只不过还要求一个时间和
如何求出至少要多少台机器:
把时间段转化成一个入点和一个出点,这样存下2*n个点,之后按坐标从小到大给这2*n个点排序,之后O(n)遍历一遍就好,遇到入点sum++, 遇到出点sum--,遍历时最大的sum便是答案,算上排序复杂度稳定nlogn(注意:排序时坐标相同的点出点优先)
时间求法也很容易:
如果当前sum=5,而ans=4(也就是当前不得不用第5台机器),那么记录下入点的时间,说明第5台机器在这个时候开始使用,同理,第1,2,6,7,8…台机器都一样,那么结束时间怎么求?倒过来再遍历一遍就好了,开始作为结束,结束作为开始,这样两者相减就是每台机器的工作时间,全加在一起就是答案
#include#include using namespace std;#define LL long longtypedef struct{ LL x; LL flag;}Point;Point s[200005];LL L[100005], R[100005];bool comp(Point a, Point b){ if(a.x ans) { ans = sum; L[sum] = s[i].x; } ans = max(ans, sum); } sum = ans = 0; for(i=n;i>=1;i--) { sum -= s[i].flag; if(sum>ans) { ans = sum; R[sum] = s[i].x; } ans = max(ans, sum); } sum = 0; for(i=1;i<=ans;i++) sum += R[i]-L[i]; printf("%lld %lld\n", ans, sum); } return 0;}