博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【贪心】【堆】AtCoder Grand Contest 018 C - Coins
阅读量:6786 次
发布时间:2019-06-26

本文共 307 字,大约阅读时间需要 1 分钟。

只有两维的时候,我们显然要按照Ai-Bi排序,然后贪心选取。

现在,也将人按照Ai-Bi从小到大排序,一定存在一个整数K,左侧的K个人中,一定有Y个人取银币,K-Y个人取铜币;

右侧的X+Y+Z-K个人中,一定有X人取金币,Y+Z-K个人取铜币。

现在,简化一下,我们把每个人的金币数和银币数减去其铜币数,然后默认取上所有人的铜币,这样不影响最终答案。

于是我们依次枚举K,计算前K个人中,银币数之和最大的Y个人,后X+Y+Z-K个人中,金币数之和最大的X个人,然后求和,更新答案。

可以用堆轻松实现。

转载于:https://www.cnblogs.com/autsky-jadek/p/7226706.html

你可能感兴趣的文章
JavaScript基础若干盲点总结
查看>>
Linux学习总结(二十八) 数据同步工具 rsync
查看>>
设置Linux系统虚拟机网卡配置全过程
查看>>
HTML 之 Dom应用
查看>>
大公司和小公司的web前端岗位,工作内容有哪些不同?
查看>>
配置httpd服务虚拟主机
查看>>
(一)2005年我的第一次软件行业创业,烧掉30万、2年时间打水漂的惨痛教训
查看>>
Win7硬盘安装方法
查看>>
python - 列表
查看>>
UIVisualEffectView用法
查看>>
springmvc+mybatis整合cms+UC浏览器文章功能
查看>>
docker安装(centos6.5_x86_64)
查看>>
mysql悲观锁与乐观锁
查看>>
struts2的配置文件的加载顺序
查看>>
装饰者模式的步骤
查看>>
ansible-playbook用法举例
查看>>
ubuntu下python2-python3版共存,创建django项目出现的问题
查看>>
2018.4.3三周第二次课
查看>>
eclipse_jee版本提供了从数据库直接生成实体类的工具!
查看>>
Error: Can't set headers after they are sent
查看>>