欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-21 17:41:56
...

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

ACM在线模板

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

题目描述

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

小黄鸭debugdebug法好呀,一边骂自己是傻逼一边飞快地找到bugbug并且ACAC

牛客的每日一题来源:
【每日一题】3月25日题目精讲 贪心、优先队列、堆
讲解还是很不错的,牛客真凉心
【牛客每日一题】tokitsukaze and Soldier 题目精讲 贪心、优先队列、堆
注:如果您通过本文,有(qi)用(guai)的知识增加了,请您点个赞再离开,如果不嫌弃的话,点个关注再走吧,日更博主每天在线答疑 ! 当然,也非常欢迎您能在讨论区指出此文的不足处,作者会及时对文章加以修正 !如果有任何问题,欢迎评论,非常乐意为您解答!( •̀ ω •́ )✧