题目链接

tokitsukaze and Soldier

题目思路:贪心+优先队列

先由大到小排列s 当新加入的人的s小于队列长度时 去除队列中v最小的人 每次加入人都会记录一下最大值 最后求出军团的vmax 实现贪心

通过代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int Max=100005;
priority_queue<LL,vector<LL>,greater<LL> > q;
struct tok
{
    LL v,s;
}a[Max];
bool cmp(tok a,tok b)
{
    return a.s>b.s;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i].v>>a[i].s;
    sort(a,a+n,cmp);
    LL tmp=0,ans=0;
    for(int i=0;i<n;i++)
    {
        tmp+=a[i].v;
        q.push(a[i].v);
        while(q.size()>a[i].s)
        {
            tmp-=q.top();
            q.pop();
        }
        ans=max(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}
```# 题目思路:贪心+优先队列
先由大到小排列s 当新加入的人的s小于队列长度时 去除队列中v最小的人 每次加入人都会记录一下最大值 最后求出军团的vmax 实现贪心
# 通过代码

include<bits/stdc++.h>

using namespace std;
#define LL long long
const int Max=100005;
priority_queue<LL,vector<ll>,greater<ll> > q;
struct tok
{
LL v,s;
}a[Max];
bool cmp(tok a,tok b)
{
return a.s>b.s;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i].v>>a[i].s;
sort(a,a+n,cmp);
LL tmp=0,ans=0;
for(int i=0;i<n;i++)
{
tmp+=a[i].v;
q.push(a[i].v);
while(q.size()>a[i].s)
{
tmp-=q.top();
q.pop();
}
ans=max(ans,tmp);
}
cout<<ans<<endl;
return 0;
}
```</ll></ll>