题解 | #网络优化#

考察知识点：贪心、优先队列

读入服务器的信息，按照 (l, r, v) 升序排序，遍历每一位用户，为每一位用户分配符合条件的服务器中 r 最小的服务器，对应的服务器的 v 值减一，若成功为用户分配服务器，则答案 ans 加一。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

struct Node
{
    int l, r, v;
    bool operator<(const Node &s) const
    {
        if (l != s.l)
            return l < s.l;
        if (r != s.r)
            return r < s.r;
        else
            return v < s.v;
    }
};

struct cmp
{
    bool operator()(const Node &a, const Node &b)
    {
        if (a.r != b.r)
            return a.r > b.r;
        else
            return a.v > b.v;
    }
};

void solve()
{
    int n, m;
    while (cin >> n >> m)
    {
        vector<Node> server(m);
        for (int i = 0; i < m; i++)
            cin >> server[i].l >> server[i].r >> server[i].v;
        sort(server.begin(), server.end());
        priority_queue<Node, vector<Node>, cmp> pq;  // 小根堆
        int cur = 0, ans = 0;
        for (int i = 1; i <= n; i++)
        {
            while (server[cur].l <= i)
            {
                pq.push(server[cur]);
                cur++;
            }
            while (!pq.empty() && (pq.top().r < i || !pq.top().v))
                pq.pop();
            if (pq.empty())
                continue;
            auto tmp = pq.top();
            tmp.v--;
            pq.pop();
            pq.push(tmp);
            ans++;
        }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}