网络优化 [贪心]

题意

游戏***有n名用户，编号从1到n，服务器共有m条服务线，每个用户最多只能登陆一条线，第i条线最多可以容纳v[i]名用户同时在线，且只能给编号在[l[i],r[i]]范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。

题解

看了一眼数据范围 < 1e4 ..
贪心即可
将当前用户分配给r更靠前的服务器，使用小根堆，遍历所有用户节点，若此节点恰好为某服务器的l值，则加入小根堆，若小根堆中服务器容量不够或r小于当前用户节点，弹出该服务器。

PS: vector动态resize范围会wa掉...不知道什么原因，还是太菜了QAQ

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

struct node{
    int l,r,v;
    bool operator<(const node &p){
        return l < p.l;
    }
};

vector<node> a;

int main()
{
    a.resize(20000);
    int n,m;
    while(cin>>n>>m){
        priority_queue<pii,vector<pii>,greater<> > pq;
        for(int i = 0;i< m;++i){
            cin>>a[i].l>>a[i].r>>a[i].v;
        }
        sort(a.begin(),a.begin()+m);
        int res = 0;
        int tp = 0;
        for(int i = 1;i <= n;++i){
            while(!pq.empty() && pq.top().first < i) pq.pop();
            while(a[tp].l == i){
                pq.push({a[tp].r,a[tp].v});
                tp++;
            }
            if(pq.empty()) continue;
            pii hd = pq.top();
            pq.pop();
            res++;
            hd.second--;
            if(hd.second > 0) pq.push(hd);
        }
        printf("%d\n",res);

    }

   return 0;
}