【每日一题】tokitsukaze and Soldier (优先队列+思维)

Solution
很奇妙的思路，看了第一篇题解才懂，先用结构体存每个士兵，然后按团数排序，再用优先队列存战力，用一个遍历cnt由n遍历到0，保证遍历保证每种可能都枚举到。
注意在枚举时，如果队列里的元素超过当前限制，出队并减去这个元素对sum的贡献。

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define ins insert
#define si size()
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }

const int manx=1e5+5;

priority_queue<ll,vector<ll>,greater<ll> >q;
struct node{
    ll fi,se;
}a[manx];
bool cmp(node a,node b){ return a.se>b.se;}

int main(){
    ll n=read();
    for(int i=1;i<=n;i++) a[i].fi=read(),a[i].se=read();
    sort(a+1,a+1+n,cmp);
    ll cnt=n,ans=0,sum=0,k=1;
    while(cnt>0){
        while(k<=n&&a[k].se==cnt) q.push(a[k].fi),sum+=a[k++].fi;
        while(q.si>cnt) sum-=q.top(),q.pop();
        ans=max(ans,sum);
        cnt--;
    }
    printf("%lld",ans);
    return 0;
}