思路:
算是比较有意思的贪心^-^
其实乍看就是简单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; }