【网络优化】题解

1.前置知识

贪心&优先队列

2.题意

有编号1-n的n个点与m条线段。其中第i条线段能容纳v[i]个编号在l[i]~r[i]之中的点，求最多有几个点能被放在线上。

3.思路

依次讨论每个点。每次将不合要求的线删去，符合要求的线加入。最后将这个点放入l最小的线段（满足贪心）即可。

4.时间复杂度

5.代码

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
int n, m;
struct node
{
    int l, r, v;
};
node line[10005];
bool cmp(node a, node b)
{
    return a.l < b.l;
}
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
int main()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        while (!pq.empty())pq.pop();
        int ans = 0;
        for (int i = 1; i <= m; i++)scanf("%d %d %d", &line[i].l, &line[i].r, &line[i].v);
        sort(line + 1, line + 1 + m, cmp);
        for (int i = 1, tot = 1; i <= n; i++)
        {
            while (!pq.empty() && pq.top().first < i)pq.pop();
            while (line[tot].l == i)
            {
                pq.push(make_pair(line[tot].r, line[tot].v));
                tot++;
            }
            if (pq.empty())continue;
            ans++;
            pair<int, int> x = pq.top();
            pq.pop();
            x.second--;
            if (x.second >= 1)pq.push(x);
        }
        printf("%d\n", ans);
    }
    return 0;
}