思路:
算是比较有意思的贪心^-^
其实乍看就是简单01背包问题,由于我太弱没想到怎么优化复杂度。
于是,换了贪心思路。
考虑一个简单问题,如果现在给定最多取K人,那么怎样最优取呢?
显然找出n个人中s[]大于等于K的人,记为S。
那我们只需要在S集合中找前K大的v值,并对其求和
敲黑板:
最暴力的方法就是,然而这道题给的人数规模为n,也是表明K最多有n种,这样暴力跑下来复杂度还是
如何优化复杂度呢?
我们把n个人的s进行从高到低排序,若,记
取值集合为S1,
取值集合为S2,
S2肯定包含S1中部分元素,这就表明在求解S2时有些元素根本不需要枚举,直接从S1中获得了,这就是优化的出发点。
用SUM记为当前优先队列的元素和,NUM记为当前优先队列的元素个数
优先队列维护v值单调不减
当我们枚举到第i个人时,我们需要把K置为该人的s,然后把这个人加到集合,更新SUM与NUM;
然后不断POP优先队列,直到NUM<=K,不断更新SUM;
总复杂度:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 +10;
struct node{
ll v;
int s;
}a[maxn];
int n;
bool cmp(node b, node c){
if(b.s == c.s) return b.v < c.v;
else return b.s < c.s;
}
void solve(){
ll ans = -1;
priority_queue<ll, vector<ll>, greater<ll>> que;
ll sum = 0;///队列元素和
int num = 0;///队列元素个数
int max_size;
for(int i = n; i >= 1; i--){
max_size = a[i].s; num++; sum += a[i].v; que.push(a[i].v);
while(num && num > max_size){sum -= que.top(); que.pop(); num--;}
ans = max(ans, sum);
}
printf("%lld\n", ans);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lld%d", &a[i].v, &a[i].s);
}
sort(a + 1, a + n + 1, cmp);
solve();
return 0;
}



京公网安备 11010502036488号