0%

【每日一题】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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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';
}

回到开头