solution
考虑枚举所选择的数中最小的。然后就是要在所有的数中找到最大的个。
所以先按照s从大到小排序,然后再维护一个小根堆,存放当前的答案。每当堆的大小大于当前的s时,就弹出元素。最后找到一个最大的答案即可。
code
/* * @Author: wxyww * @Date: 2020-05-05 20:52:24 * @Last Modified time: 2020-05-05 21:01:26 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 200010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,s; }a[N]; bool cmp(const node &A,const node &B) { return A.s > B.s; } priority_queue<int,vector<int>,greater<int> >q; int main() { int n = read(); for(int i = 1;i <= n;++i) { a[i].v = read();a[i].s = read(); } sort(a + 1,a + n + 1,cmp); ll ans = 0,anss = 0; for(int i = 1;i <= n;++i) { q.push(a[i].v); ans += a[i].v; while(q.size() > a[i].s) { ans -= q.top();q.pop(); } anss = max(ans,anss); } cout<<anss<<endl; return 0; }