E2. Voting (Hard Version)(思维)

2024-01-19 14:40
文章标签 思维 version hard voting e2

本文主要是介绍E2. Voting (Hard Version)(思维),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

 

有 n 个人,每个人有 mi 和 pi ,mi 代表着如果有 mi 个人投票给他,那么他就免费投票给他,否则你需要花费pi的代价来收买他。请问最少花费多少使得所有人都投他。

看到 m 数组的数据范围,m 数组作为数组下标应该是没得跑了,有贪心策略我们应该选择 pi 尽量少的那些人,但是同时要照顾到 m 数组。

因为要贿赂的总人数我们不知道,但借用优先队列(小根堆),将目前为止的最少需要的贿赂人数贿赂。

向题目中提到的:m :1 2 2 4 5,只需贿赂 m[5] 即可,这样贪心策略就出来了:把这些 m 偏大的人先贿赂了,贿赂的最少人数为 n-i (i 为 m 数组的下标)  

    vector<int> v[N];int main()
{//IOS;rush(){sd(n);for(i=0;i<=n;i++) v[i].clear();for(int i=1,p;i<=n;i++){sdd(m,p);v[m].pb(p);}priority_queue< int ,vector<int>,greater<int> >q;ll ans=0;for(i=n;i>=0;i--){int len=v[i].size();for(j=0;j<len;j++) q.push(v[i][j]);while(q.size()>n-i){//到此时为止必须有 n-i 个人为其投票 ans+=q.top();q.pop();}}pll(ans);}//PAUSE;return 0;
}

 

这篇关于E2. Voting (Hard Version)(思维)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/622744

相关文章

Maven创建项目中的groupId, artifactId, 和 version的意思

文章目录 groupIdartifactIdversionname groupId 定义:groupId 是 Maven 项目坐标的第一个部分,它通常表示项目的组织或公司的域名反转写法。例如,如果你为公司 example.com 开发软件,groupId 可能是 com.example。作用:groupId 被用来组织和分组相关的 Maven artifacts,这样可以避免

Jenkins 通过 Version Number Plugin 自动生成和管理构建的版本号

步骤 1:安装 Version Number Plugin 登录 Jenkins 的管理界面。进入 “Manage Jenkins” -> “Manage Plugins”。在 “Available” 选项卡中搜索 “Version Number Plugin”。选中并安装插件,完成后可能需要重启 Jenkins。 步骤 2:配置版本号生成 打开项目配置页面。在下方找到 “Build Env

颠覆你的开发模式:敏捷思维带来的无限可能

敏捷软件开发作为现代软件工程的重要方法论,强调快速响应变化和持续交付价值。通过灵活的开发模式和高效的团队协作,敏捷方法在应对动态变化和不确定性方面表现出色。本文将结合学习和分析,探讨系统变化对敏捷开发的影响、业务与技术的对齐以及敏捷方法如何在产品开发过程中处理持续变化和迭代。 系统变化对敏捷软件开发的影响 在敏捷软件开发中,系统变化的管理至关重要。系统变化可以是需求的改变、技术的升级、

Learn ComputeShader 09 Night version lenses

这次将要制作一个类似夜视仪的效果 第一步就是要降低图像的分辨率, 这只需要将id.xy除上一个数字然后再乘上这个数字 可以根据下图理解,很明显通过这个操作在多个像素显示了相同的颜色,并且很多像素颜色被丢失了,自然就会有降低分辨率的效果 效果: 但是这样图像太锐利了,我们加入噪声去解决这个问题 [numthreads(8, 8, 1)]void CSMain(uint3 id

0906作业+思维导图梳理

一、作业: 1、创捷一个类似于qq登录的界面 1)源代码 #include "widget.h"#include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget){ui->setupUi(this);//QPushbutton:登录、退出this->join = new QP

HDU 1097 A hard puzzle(规律)

题目: http://acm.hdu.edu.cn/showproblem.php?pid=1097 题意: 求a的b次方的最后一位。 题解: 直接从例子入手, 第一组数据 7 66,结果如下(只要最后一位所以模10) 7 9 3 1 7 9··· 循环节为4,即结果在4个数值内循环出现。 第二组数据 6 800,结果如下 6 6 6 6··· 循环节为1 ···

[机缘参悟-222] - 系统的重构源于被动的痛苦、源于主动的精进、源于进化与演进(软件系统、思维方式、亲密关系、企业系统、商业价值链、中国社会、全球)

目录 前言:系统的重构源于被动的痛苦、源于主动的精进、源于进化与演进 一、软件系统的重构 1、重构的定义与目的 2、重构的时机与方法 3、重构的注意事项 4、重构的案例分析 二、大脑思维的重构 1、大脑思维重构的定义 2、大脑思维重构的方法 3、大脑思维重构的挑战与前景 三、认知的重构 1、定义 2、目的 3、方法 四、实例 五、总结 四、婚姻家庭的重构 1、婚

Unsupported major.minor version 52.0 错误解决方法

自己前些天的项目突然出现这个问题,经过仔细排查,发现有两个原因都会导致这个问题。 第一个就是POM文件中的dependency重复,如果使用的是maven导入,重复写入dependency就会出现该错误。 第二个是版本不匹配,即所引用的jar包太新,并不匹配你的jdk,因为我们正常用的都是jdk7,但是现在已经更新到jdk10了,好多最新版本最新版本的jar包都是基于最新的jdk编写,所以可以

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

散户炒股票为什么进步慢,学习程序化交易思维

炒股自动化:申请官方API接口,散户也可以 python炒股自动化(0),申请券商API接口 python炒股自动化(1),量化交易接口区别 Python炒股自动化(2):获取股票实时数据和历史数据 Python炒股自动化(3):分析取回的实时数据和历史数据 Python炒股自动化(4):通过接口向交易所发送订单 Python炒股自动化(5):通过接口查询订单,查询账户资产 散户炒股的常见难题