BZOJ 4425: [NWERC2015]Assigning Workstations – [贪心/堆]


题目传送门(BZOJ)

题解 :

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

代码 :

#include 
#include 
#include 
#include 
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 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原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注