【每日一题】网络优化 题解

Description

《梦三国2》是一款3D MOBA类网游。游戏继承《梦三国》的三国文化背景和基础玩法，并加入许多全新地图和全新竞技玩法。由于人气高，游戏在线人数与日俱增，我们知道当在线人数不断增长的时候，会给服务器带来巨大的压力。
已知该游戏***有n名用户，编号从1到n，服务器共有m条服务线，每个用户最多只能登陆一条线，第i条线最多可以容纳v[i]名用户同时在线，且只能给编号在[l[i],r[i]]范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。

Solution

思路:贪心
以r坐标为第一关键字，l坐标为第二关键字，val为第三关键字进行排序，理性感受一下就是尽量把每个区间应用到前面的一些用户，使得每个区间能尽量应用到后面的用户。
直接搞了个的做法，但是我没看到有多组输入的条件?然后wa了，看了下大家都多组输入，以为会TLE，没想到过了....
大家优先队列，网络流都写得挺详细的，这里就只提供一种时间复杂度fake的暴力做法吧(逃

update:
补充一下优先队列的做法吧,从1到n遍历，当有包含这个点的区间就放在优先队列里，保证队首是右端点最小的，然后每次更新队首的val,若当前遍历的点已经超出队首的范围或队首的val为0，则弹出。比较烦的是要写两个结构体?优先级各不相同。
时间复杂度

Code(暴力 80ms)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
struct node {
  int l, r, val;
  bool operator < (const node &s) {
    if(r != s.r) return r < s.r;
    if(l != s.l) return l < s.l;
    return val < s.val;
  }
}a[N];
bool vis[N];
int main() {
  int n, m; 
  while(cin >> n >> m) {
    for(int i = 1; i <= n; i++) vis[i] = 0;
    for(int i = 1; i <= m; i++) cin >> a[i].l >> a[i].r >> a[i].val;
    sort(a + 1, a + 1 + m);
    for(int i = 1; i <= m; i++) {
      int l = a[i].l, r = a[i].r;
      int cnt = a[i].val;
      for(int j = l; j <= r; j++) {
        if(!vis[j] && cnt) {
          --cnt, vis[j] = 1;
        }
      }
    }
    int ans(0);
    for(int i = 1; i <= n; i++) ans += (vis[i]);
    cout << ans << '\n';
  }
  return 0;
}

Code(优先队列 40ms)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
struct node {
  int l, r, val;
  node(int _l = 0, int _r = 0, int _val = 0): l(_l), r(_r), val(_val){}
  bool operator < (const node &s) const {
    if(l != s.l) return l < s.l;
    if(r != s.r) return r < s.r;
    return val < s.val;
  }
}a[N];
struct qnode {
  int l, r, val;
  qnode(int _l = 0, int _r = 0, int _val = 0): l(_l), r(_r), val(_val){}
  bool operator < (const qnode &s) const {
    if(r != s.r) return r > s.r;
    return val > s.val;
  }
};
int main() {
  int n, m;
  while(cin >> n >> m) {
    int ans = 0;
    for(int i = 1; i <= m; i++) {
      cin >> a[i].l >> a[i].r >> a[i].val;
    }
    sort(a + 1, a + 1 + m);
    priority_queue<qnode> q;
    int cur = 1;
    for(int i = 1; i <= n; i++) {
      while(a[cur].l == i) {
        q.push(qnode(a[cur].l, a[cur].r, a[cur].val));
        cur++;
      }
      while(!q.empty() && (q.top().r < i || !q.top().val)) q.pop();
      if(q.empty()) continue;
      ans++;
      auto tmp = q.top(); q.pop();
      tmp.val--;
      q.push(qnode(tmp));
    }
    cout << ans << '\n';
  }
  return 0;
}