[每日一题]3.24 tokitsukaze and Soldier

题目网址:https://ac.nowcoder.com/acm/problem/50439

涉及知识点:

  • 优先队列/贪心

做法:

  • 每个士兵都有战力Vi和一个限制Si,我们先按照每个士兵的Si从大到小进行排序
  • 然后我们根据排好序的士兵遍历
  • 因为士兵的Si从大到小,所以遍历的过程中,当前遍历的士兵对应的si一定是最小
  • 所以我们可以维护一个大小由Si较小的优先队列
  • 如果队列大小小于当前遍历士兵的Si,就扔到优先队列里,一旦士兵的人数超过限制,出队,直到队列大小等于当前士兵的Si减一

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
struct node{
    ll v;
    int s;
};
node a[maxn];
bool cmp(node p1,node p2){
    return p1.s > p2.s;
}
priority_queue< ll ,vector<ll>,greater<ll> > q;//小根堆
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld %d",&a[i].v,&a[i].s);
    }
    sort(a+1,a+1+n,cmp);
    ll ans = 0 , cnt = 0;
    for(int i=1;i<=n;i++){
        while(q.size() >= a[i].s){
            cnt -= q.top();
            q.pop();
        }
        q.push(a[i].v);
        cnt += a[i].v;
        ans = max(ans , cnt);
    }
    printf("%lld\n",ans);
    return 0;
}
acm菜鸡日常 文章被收录于专栏

一般写一些打过的比赛题解以及不会的算法

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 14:00
点赞 评论 收藏
分享
宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
06-14 19:09
门头沟学院 Java
darius_:给制造业搞的,什么物料管理生产管理,设备管理点检,最最关键的就是一堆报表看板。个人觉得没啥技术含量都是些基本的crud,但是业务很繁琐那种
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务