Codeforces-20152016-northwestern-european-regional-contest-nwerc-A题

一、题目

二、题意

　　（1）一开始理解成：它最多需要开多少台电脑。同时，我又有个疑问，既然是最多需要开多少台，那不变成了总共有几个人开几台是最大的结果。然后，WA了无数发。直到比赛结束。。。。。。其实说到底还是不明白题目意思。

　　（2）真正的意思是：这个人最多可以节省多少台不开。也就是说，能共同用一台就共同用一台，没办法的情况下才去开新机子。问最多可以有多少台不开。也就是人数n - 最少需要开多少台机子。

三、思路

　　用闭区间记录输入数据，按区间左边（人来的时刻）从小到大排序（如果左边相同，则按右边从小到大排序）。用优先队列存储待机（没锁的机子）的区间段（从使用者下机到机器自动锁这一闭区间），区间左边越靠前的，优先级越高（为什么按左边？因为这些待机区间段长度相等）。很好理解嘛，如果不先使用那些快要锁屏的机子，那肯定会浪费一些快要锁屏的机子，而要开更多的新机子，不划算。就像吃东西一样。先把快过期的东西吃掉，再吃保质期更长的。然后遍历所有区间，对于某个上机者，先在队列中找找有没有在待机的空机子，如果没有，没办法，开一台新的。有的话，看看最早过期的那个机器的开始时刻，如果比当前上机者的上机时间晚，说明这个人来早了，也没办法，必须开台新的。另外，如果队列首元素的结束时间比当前上机者的上机时间要早，说明这个人来晚了，那就把队首元素移除掉，然后看看下一个队首元素如何。如果队首元素的起始时间比上机者的上机时间早，说明有剩余机子（为什么不用同时判断上机者的上机时间是不是比队首元素的结束时间小或等于？因为如果大于，在前一个判断中就过滤掉了，能走到这步判断的队首元素都是满足上机者的上机时间小于等于队首元素的结束时间的），这个人就坐过去，结果计数器加1。当前，只要有人上机，那就往队列中加入当前这个人的下机时刻到机器自动锁时刻的区间。

　　另外，注意一点优先队列的用法，这个比较绕，到底怎么才是优先，需要搞明白。

四、源代码

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;
typedef long long LL;
typedef __int64 I64;
const int MAXN = 3e5 + 10;
I64 n, m;
typedef struct Foo {
    I64 s, t;
    Foo() {
        s = 0, t = 0;
    }
    Foo(I64 _s, I64 _t) {
        s = _s, t = _t;
    }
    bool operator < (Foo f) const {
        if(s == s)return t > f.t;
        else return s > f.s;
    }
} Interval;
Interval itv[MAXN];
priority_queue<Interval> que;


bool cmp(Interval i1, Interval i2) {
    if(i1.s == i2.s)return i1.t < i2.t;
    else return i1.s < i2.s;
}

void solve() {
    sort(itv + 1, itv + n + 1, cmp);
    while(!que.empty())que.pop();
    int saved = 0;
    for(int i = 1; i <= n; ++i) {
        while(!que.empty() && itv[i].s > que.top().t)que.pop();
        if(!que.empty() && itv[i].s >= que.top().s) {
            saved++;
            que.pop();
        }
        que.push(Interval(itv[i].t, itv[i].t + m));
    }
    printf("%d\n", saved);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("Ainput.txt", "r", stdin);
    freopen("Aoutput2.txt", "w", stdout);
#endif // ONLINE_JUDGE
    I64 a, b;
    while(~scanf("%I64d%I64d", &n, &m)) {
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d%I64d", &a, &b);
            itv[i].s = a, itv[i].t = a + b;
        }
        solve();
    }
    return 0;
}

Codeforces-20152016-northwestern-european-regional-contest-nwerc-A题

相关推荐