题意:
选择k个士兵,在满足总共的mins>=k的情况下,让他们的值和最大
思路:
是真的菜,这么简单的贪心都想不到,假设我们已经知道了最后选取k个士兵,那么我们可以优先选择s>=k最大的k个士兵,然后我们将士兵们排序嘛,然后按照值放进堆中,如果堆的大小大于限制,把最垃圾的t出来!
ac代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
struct node{
ll x;
ll y;
bool operator <(const node&W)const
{
if(y!=W.y)
return y>W.y;
return x<W.y;
}
}q[N];
ll dp[N];
int n;
priority_queue<ll,vector<ll>,greater<ll>>Q;
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin>>q[i].x>>q[i].y;
}
sort(q+1,q+1+n);
ll res=0;
ll ans=0;
for(int i=1;i<=n;i++)
{
res+=q[i].x;
Q.push(q[i].x);
while(Q.size() && Q.size()>q[i].y)
{
auto t=Q.top();
Q.pop();
res-=t;
}
ans=max(ans,res);
}
cout<<ans<<endl;
}