【牛客每日一题】tokitsukaze and Soldier 题目精讲 贪心、优先队列、堆

链接：https://ac.nowcoder.com/acm/problem/50439
来源：牛客网

ACM在线模板

今天才发现牛客推出了一个每日一题的版块，3月25号就开始了，今天才发现，赶紧补救一下。

题目描述

在一个游戏中，$tokitsukaze$tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。 第i个士兵的战力为$v[i]$v[i]，团的战力是团内所有士兵的战力之和。 但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过$s[i]$s[i]。(如果不选第i个士兵，就没有这个限制。) $tokitsukaze$tokitsukaze想知道，团的战力最大为多少。
输入描述:
第一行包含一个正整数$n(1≤n≤10^5)$n(1≤n≤105)。接下来n行，每行包括2个正整数$v,s(1≤v≤10^9,1≤s≤n)$v,s(1≤v≤109,1≤s≤n)。
输出描述:
输出一个正整数，表示团的最大战力。

示例1

输入

2
1 2
2 2

输出

3

示例2
输入

3
1 3
2 3
100 1

输出

100

这道题要求武力值总和最大，但是每个人都有两个属性，一个是个人的武力值和队友数，如果直接贪心地按照武力值排序，那么每个人的队友数不同，会使得整个队伍的人数忽上忽下，不是线性的很难处理，所以这道题应该按照队友数排序，先选队友数多的人，然后每次选新人因为新人的队友数一定更小说明要丢掉几个人，那么用优先队列按照武力值排序，先进队的人的队友数一定比后进入的人的队友数大，所以不用担心会有问题，每次把武力值最小的人丢出去，然后用max在整个过程中找最大值输出即可。
这题虽然简单但是思路还是值得注意的。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=1e5+7;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m;
struct node
{
    ll v,s;
    bool operator<(const node &t)const
    {
        return s>t.s;
    }
}a[N];
priority_queue<ll,vector<ll>,greater<ll> >q;

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&a[i].v,&a[i].s);
    sort(a+1,a+1+n);
    ll ans=0,tmp=0;
    over(i,1,n)
    {
        tmp+=a[i].v;
        q.push(a[i].v);
        while(q.size()>a[i].s)
        {
            tmp-=q.top();
            q.pop();
        }
        ans=max(ans,tmp);
    }
    printf("%lld\n",ans);
    return 0;
}

小黄鸭$debug$debug法好呀，一边骂自己是傻逼一边飞快地找到$bug$bug并且$AC$AC

牛客的每日一题来源：
【每日一题】3月25日题目精讲 贪心、优先队列、堆
讲解还是很不错的，牛客真凉心

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧