题意
游戏***有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; }