题目传送门(BZOJ)

题解 :

先把所有人排个序, 从时间小的开始算答案
对于一个人, 若想让它使用之前留下的, 那么肯定要贪心的选所有可以使用的中最早的.
我们用堆维护这个东西, 对于这个人, 把所有时间太长的都弹掉,
因为我们按时间排了序, 对于这个人没用意味着对后面的所有人都没用
之后如果可以选, 即堆中有元素, 且堆顶元素的时间不大于这个人来上班的时间, 那么累加答案.
然后把这个人离开的时间压到堆里
挺好想挺简单的一个贪心~

代码 :

#include <queue>#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(ch < 48) ch = nc(); while(ch > 47) x = (((x<<2)+x)<<1)+(ch^48), ch = nc(); return x;}struct LINE { int l, r; int operator < (const LINE &A) const {return l < A.l; }}a[300001];priority_queue<int> q;int main() { int n = rd(), m = rd(), ans = 0; register int i ; for(i = 1; i <= n; i ++ ) a[i].l = rd(), a[i].r = a[i].l+rd(); sort(a+1, a+n+1); for(i = 1; i <= n; i ++ ) { while(!q.empty() && -q.top()+m < a[i].l) q.pop(); if(!q.empty() && -q.top() <= a[i].l) q.pop(), ans++; q.push(-a[i].r); } printf("%d\n", ans); return 0;}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<