网络优化

题目大意

有一个区间，有条网络，第条网络的服务区间为，但是它只能提供个人的服务。
问：如何分配才能使得同一时间上线的人数最多？

分析

那么就考虑对于每一个点它是否能够被覆盖到，贪心即可。
那么贪心过程就可以是从左到右枚举区间上的每一个点，然后在符合条件的服务器中扣除一个人的服务。
那么如何来维护符合条件的服务器呢？

• 先将左右的服务器按左端点从小到大排序
• 将所有的的服务器加入到优先队列中
• 把所有或者不能再提供服务的服务器弹出
  • 如果此时优先队列不为空，那么这个人可以上线，有的贡献，将这个服务器的服务人数减一
  • 如果此时优先队列为空，那么这个人无法上线了，没有贡献

时间复杂度大概是的

Code

#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 10;

inline int __read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <='9'; o = getchar()) 
        x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

struct Node
{
    int l, r, v;
    bool operator < (const Node &T) const{
        if (l == T.l && r == T.r) return v < T.v;
        else if (l == T.l) return r < T.r;
        return l < T.l;
    }
}server[maxn];

struct Tree
{
    int rest, r;
    Tree () {}
    Tree (int rest, int r) : rest(rest), r(r) {}
    bool operator < (const Tree &T) const {
        if (r == T.r) return rest > T.rest;
        return r > T.r;
    }
};

int n, m;
int main()
{
    while (~scanf ("%d %d", &n, &m)) {
        for (int i = 1; i <= m; ++i)
            server[i].l = __read(), server[i].r = __read(), server[i].v = __read();
        sort (server + 1, server + m + 1);
        priority_queue <Tree> Q;
        int cnt(1), ans(0);
        for (int i = 1; i <= n; ++i) {
            while (server[cnt].l == i) {
                Q.push(Tree(server[cnt].v, server[cnt].r));
                ++cnt;
            }
            while (!Q.empty() && (Q.top().r < i || !Q.top().rest))
                Q.pop();
            if (Q.empty()) continue;
            Tree T = Q.top();
            T.rest--;
            Q.pop();
            Q.push(T);
            ++ans;
        }
        printf ("%d\n", ans);
    }
}