【贪心】【堆】AtCoder Grand Contest 018 C - Coins
2024-10-20 16:08:38
只有两维的时候，我们显然要按照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个人，然后求和，更新答案。
可以用堆轻松实现。
最新文章
- Linux下java进程CPU占用率高分析方法
- 场景9 深入RAC运行原理
- Freemarker list标签,list数据判断使用
- python最简单的http服务器
- 论文笔记之：Pedestrian Detection aided by Deep Learning Semantic Tasks
- C# progressbar 用法
- Android的TextView与Html相结合的用法
- python笔记——第二天
- C#图解教程 第二十二章 异常
- js工具函数《转载收藏》
- Docker镜像的实现原理
- 有人WIFI模块使用详解
- Java开发笔记（六十三）双冒号标记的方法引用
- Asp.net core 环境配置
- Linux（centos 7）配置tomcat8、JDK1.8、lighttpd、ngnix、mysql
- 【SVN】SVN的trunk、branches、tag的使用以及分支的概念
- IOS 视频流
- 关于 initWithNibName 和 loadNibNamed 的区别和联系
- 使用Facade模式更新库存、确认订单、采取打折、确认支付、完成支付、物流配送
- WPF多线程访问控件