【每日一题】tokitsukaze and Soldier 题解

Solution

非常显然的离线+优先队列求解，先处理更加“宽容”的人（希望士兵团不超过的人数更多的人），那么那些不那么“宽容”的被分配到团中时，比这个人更加“宽容”的人也能分配到团中。

限定一个值 $k$ ，让 $s[i]\ge k$ 都堆在一起后，选择前 $k$ 大的 $v[i]$ 求和即是此时所能安排的最大值。这是经典的topK问题。

$k$ 的取值有 $n$ 个，所以直接枚举 $k$ 的复杂度是 $O(n^2)$ 的。但如果从 $s[i]$ 大的开始安排的话，会发现枚举的元素是在原来的基础上增加而已。那么问题就变成了动态的topK问题了。复杂度变为了 $O(n\log(n))$ 。

他给的输入不是按照 $s[i]$ 递减的顺序给的，那么排一下序就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n; cin >> n;
  priority_queue<int, vector<int>, greater<int>> q;
  vector<pair<int, int>> v(n);
  for(int i = 0; i < n; i++) {
    cin >> v[i].second >> v[i].first;
  }
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  long long sum = 0, ans = 0;
  for(int i = n, j = 0; i >= 1; i--) {
    while(j < n && v[j].first >= i) {
      q.push(v[j].second);
      sum += v[j].second;
      j++;
    }
    while(int(q.size()) > i) {
      sum -= q.top();
      q.pop();
    }
    ans = max(ans, sum);
  }
  cout << ans << '\n';
}