牛客 tokitsukaze and Soldier

题目分析

1.首先要注意题目给的范围，所以我们要用long long 去定义武力值
2.在排序的时候我们让要求人数多的士兵排在前头
3.接下来我们就一次枚举每一种情况，最后得出最大值，我们用一个优先队列去存入每一个士兵的武力值，并且在每一次存入的时候都去判断是否满足当前士兵的要求（最多s[i]个人），如果超出我们就除去栈顶的元素，因为我们定义的是小根堆，排序规则为从小到大，栈顶的元素肯定是最小的，这样我们就能兼顾每一位士兵的要求，从而求出武力值最大的团队去打副本

AC代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
struct node
{
   ll v;
   int s;
   bool operator<(const node x) const
   {
      return s > x.s; //结构体排序让s[i]多的在前面
   }
} w[maxn];
priority_queue<ll, vector<ll>, greater<ll>> q; //小根堆
//priority_queue<ll>q    默认是大根堆
int main()
{
   int n;
   while (~scanf("%d", &n))
   {
      for (int i = 1; i <= n; ++i)
         scanf("%lld%d", &w[i].v, &w[i].s);
      sort(w + 1, w + n + 1); //排序方便后续计算
      ll cnt = 0, ans = 0;
      for (int i = 1; i <= n; ++i)
      {
         cnt += w[i].v;
         q.push(w[i].v);           //用堆去维护武力值
         while (q.size() > w[i].s) //每次加入的时候都判断是否满足当前士兵的要求
         {
            cnt -= q.top();
            q.pop();
         }
         ans = max(ans, cnt); //计算最值
      }
      printf("%lld\n", ans);
   }
   return 0;
}

也可以参考我的博客 https://blog.csdn.net/qq_44833724/article/details/105879452