【ECNU】3496. 贪吃的 xjj 和贪心的 oxx(C++)
目录
题目
输入格式
输出格式
样例
提示
思路
代码
题目
单点时限: 2.0 sec
内存限制: 256 MB
oxx 与 xjj 终于到了 Xiamen,他们第一件事就是去吃当地著名的特产椰子饼。
他们共买了 n 盒礼盒,第 i 盒含 ai 块椰子饼。oxx 与 xjj 约定让 oxx 来分配这 n 盒椰子饼。
为了讨好 xjj ,oxx 决定自己的椰子饼的总数要不大于 xjj 的总数。但是 oxx 知道贪吃的 xjj 会忍不住拆开一盒吃了,因此贪心的 oxx 希望: xjj 无论拆开哪一盒她自己的椰子饼后,oxx 拥有的椰子饼总数要不小于 xjj 剩余的椰子饼总数。oxx 想知道是否存在一个分配方案能够满足他的要求,如果存在输出 Yes
,并输出方案,否则 No
。
如果上述题意让你感到很困惑的话,我们要求的是 S=a1,a2,…,an 这一多重集的一个非空子集 S′=ai1,ai2,…,aik,使得(Sum(S′)≤Sum(S−S′))∧(∀t∈S−S′,Sum(S′)≥Sum(S−S′)−t)
记多重集 Sum(A) 表示多重集 A 所有元素的和。特别地,Sum(∅)=0。
更困惑了吗?Here we go.
输入格式
第一行一个整数 n (2≤n≤106)。
接下去一行,n 个整数 a1,a2,…,an (1≤ai≤106) 分别表示每盒椰子饼的个数。
输出格式
第一行一个字符串,Yes
表示存在这样的方案,No
表示不存在。
若为 Yes
,第二行一个整数 m (1≤m≤n−1),表示 oxx 自己选的椰子饼数量。
第三行 m 个用空格隔开的整数,表示 oxx 所选取的椰子饼的编号,下标从 1 开始,编号不能有重复,顺序无所谓。
样例
input
2 1 2
output
Yes 1 1
input
7 4 5 4 5 4 5 4
output
Yes 3 2 4 6
提示
样例 2:在 oxx 挑了 5、5、5 这三个之后,总和 15 不超过 xjj 拿到的 4、4、4、4 的总和 16,而且无论 xjj 偷吃了哪个(反正都是 4),15 总大于等于 12。
思路
难度评级:⭐️⭐️⭐️⭐️
步骤:
个人认为这一道非常好的使用贪心算法的题目。
首先把一堆饼干分给oxx和xjj的问题可以转化为将一堆饼干分成一大一小的两堆饼干,然后将小的一堆分给oxx即可,所以问题就是如何分出这样的一大一小两堆符合题目要求的饼干。
一开始两堆饼干肯定都是0,也就是两堆饼干都是一样大,此时我们可以随便取其中的一堆看成是小堆,另一堆看成是大堆。
然后如果我们是不停地向大堆里面放饼干,那么大堆会永远是大堆,小堆永远是小堆,不会有任何变化,而且这肯定不符合题意,所以一定是永远都往小堆里面方饼干,这样局势才有可能翻转,有变化;那么问题就又转化为我们应该向小堆里面放怎样的饼干。
因为题目要求最终大堆里面取出任意一个饼干盒后都会变成小堆,即只要取出最小的饼干盒后变成小堆就行;
而大堆在放入最后一盒饼干前肯定是小堆,所以它才会被选中要放饼干盒,放入饼干盒后就变成了大堆,因此反过来理解就是:现在的大堆去掉最后放入的一盒饼干后就变成了小堆,所以我们此时应该希望这最后放入的一盒饼干就是最小的饼干盒,因此我们应该将饼干盒倒序存储,然后以这样的顺序分饼干盒,这样就可以保证两个堆中最后放入的饼干盒永远都是当前堆中最小的饼干盒。
tips:
关于对饼干盒的排序,排序的根据应该是饼干盒中饼干的数量,但是我们需要记录下饼干数量对应的饼干盒的id,所以有两种方案:
1. 用结构体或者pair类型存储饼干盒id和饼干盒中的饼干数量,然后再对它们所构成的数组排序
2. 两个数组,一个记录饼干盒id,一个记录饼干盒中饼干的数量,然后对饼干盒id根据饼干数量进行倒序排序(我的代码就是这种方案)
代码
#include <iostream>
#include <algorithm>
#include <set> using namespace std;
typedef long long ll;const int MAX=1e6+10;
int value[MAX];// 存放饼干数
int id[MAX];// 存放饼干盒的idbool cmp(const int &x,const int &y) {return value[x]>value[y];
}int main(int argc, char** argv) {int n;cin>>n;// 输入饼干数for(int i=0;i<n;i++) {cin>>value[i];id[i]=i;} // 根据饼干盒中饼干的数量,对饼干盒id进行倒序排序sort(id,id+n,cmp);ll x=0,y=0;// 两堆饼干盒的饼干数量set<int> xId,yId;// 两堆饼干盒的id们 // 不断地把较大的饼干盒分给较小的堆for(int i=0;i<n;i++) {if(x<=y) {// x是小堆时,第i大的饼干盒就给它 x+=value[id[i]];xId.insert(id[i]+1);// 加一是因为饼干盒的id是从1开始算的 } else {// y是小堆时y+=value[id[i]];yId.insert(id[i]+1); } } // 一定是有符合要求的分配的cout<<"Yes"<<endl;// 较小的堆是oxx的if(x<=y) {cout<<xId.size()<<endl;for(int s:xId) cout<<s<<" ";} else {cout<<yId.size()<<endl;for(int s:yId) cout<<s<<" ";}return 0;
}
相关文章:
【ECNU】3496. 贪吃的 xjj 和贪心的 oxx(C++)
目录 题目 输入格式 输出格式 样例 提示 思路 代码 题目 单点时限: 2.0 sec 内存限制: 256 MB oxx 与 xjj 终于到了 Xiamen,他们第一件事就是去吃当地著名的特产椰子饼。 他们共买了 n 盒礼盒,第 i 盒含 ai 块椰子饼。oxx 与 xjj 约定让 oxx …...

【iOS】设置背景渐变色
drawRect函数 主要负责iOS的绘图操作,程序会自动调用此方法进行绘图。我在这个函数中绘制渐变背景色。 方法定义: -(void)drawRect:(CGRect)rect; 重写此方法,执行重绘任务-(void)setNeedsDisplay; 标记为需要重绘,异步调用dra…...

Scrapy框架(高效爬虫)
文章目录一、环境配置二、创建项目三、scrapy数据解析四、基于终端指令的持久化存储1、基于终端指令2、基于管道3、数据同时保存至本地及数据库4、基于spider爬取某网站各页面数据5、爬取本页和详情页信息(请求传参)6、图片数据爬取ImagesPipeline五、中…...

程序设计语言-软件设计(二十一)
数据结构与算法(二十)快速排序、堆排序(四)https://blog.csdn.net/ke1ying/article/details/129269655 这篇主要讲的是 编译与解释、文法、正规式、有限自动机、表达式、传值与传址、多种程序语言特点。 编译的过程 解释型 和 编译型 编译型过程&#…...

【小破站下载工具】Python tkinter 实现网站下载工具,所有数据一键获取
目录前言开发环境本次项目案例步骤先展示下完成品的效果界面导入模块先创建个窗口功能按键主要功能代码编写功能一功能二功能三前言 最近很多同学想问我,怎么把几个代码的功能集合到一起? 很简单,写一个界面就行了,想要哪个代码…...
C51---IO口状态翻转
1.example #include "reg52.h" #include "intrins.h" //main.c(11): error C264: intrinsic _nop_: declaration/activation error,?????????? sbit led1 P3^7;//????,??????? sbit key1 P2^1; sbit key2 P2^0; void Delay50ms()…...
2023年春【移动计算技术】文献精读(一)-1 ||| 附:【Markdow语法】向上取整 向下取整。
沉默着走了有 // 多遥远 // 抬起头 // 蓦然间 // 才发现 // 一直倒退 // 倒退到原点 // 倔强坚持 // 对抗时间 “在光芒万丈之前,我们都要欣然接受眼下的难堪和不易,接受一个人的孤独和偶然无助,认真做好眼前的每件事,你想要的都会有。”——毕淑敏 🎯作者主页:追光者♂…...
Java 包装类的二进制操作
Integer 位翻转 位翻转就是将二进制左边的位与右边的位进行互换,reverse 是按位进行互换, reverseBytes 是按 byte 进行互换。 public static int reverse(int i)public static int reverseBytes(int i)来看个例子: int a 0x12345678; S…...

CSS居中之 { left:50%; top:50%; transform:translate(-50%,-50%); }
CSS居中之 { left:50%; top:50%; transform:translate(-50%,-50%); } left:50%; top:50%; transform:translate(-50%,-50%); left:50%; top:50%; transform:translate(-50%,-50%);也可以写成: left:50%; top:50%; translate: -50% -50%; left:50%; top:50%; translate: -50%…...

AcWing 4868. 数字替换(DFS + 剪枝优化)
AcWing 4868. 数字替换(DFS 剪枝优化)一、问题二、思路三、代码一、问题 二、思路 题目中要求变换次数最小,其实第一印象应该是贪心,即我们每一次都去成各位中最大的那个数字。但是这个想法很容易推翻。因为你这次乘了一个最大的…...

【教学典型案例】01.redis只管存不管删除让失效时间删除的问题
目录一:背景介绍二:redis1)redis数据类型①String(字符串)②Hash(哈希)③List(列表)④Set(集合)2)缓存同步①设置有效期②同步双写③异步通知3&am…...
电话号码管理
电话号码管理 文章目录 电话号码管理综述链表结构initcreatedeleteallfreeANSI颜色转义颜色列表如下:字背景颜色范围:40--49 字颜色: 30--39输出特效格式控制:光标位置等的格式控制:Makefile顶层Makefilescripts Makefilesearch main init include display delete create all…...
Shell 教程
Shell 是一个用 C 语言编写的程序,它是用户使用 Linux 的桥梁。Shell 既是一种命令语言,又是一种程序设计语言。 Shell 是指一种应用程序,这个应用程序提供了一个界面,用户通过这个界面访问操作系统内核的服务。 Ken Thompson 的…...

Shader 阴影
阴影生成原理 以平行光为例,把相机移动到光源位置,计算阴影映射纹理(shadowmap),这张shadowmap本质上是一张深度图,它记录了从该光源的位置出发、能看到的场景中距离它最近的表面位置(深度信息&…...

【冲刺蓝桥杯的最后30天】day2
大家好😃,我是想要慢慢变得优秀的向阳🌞同学👨💻,断更了整整一年,又开始恢复CSDN更新,从今天开始更新备战蓝桥30天系列,一共30天,如果对你有帮助或者正在备…...

docker系列1:docker安装
传送门 docker官网地址: Docker: Accelerated, Containerized Application Development 安装地址:Install Docker Engine docker hub地址 docker hub:Docker 安装步骤 前置条件 由于安装docker,需要根据操作系统版本选择…...

内核角度谈谈Linux进程和线程
目录前言内核对进程和线程的表示创建进程的过程创建线程的过程创建进程和线程的异同揭秘 do_fork 系统调用结论前言 昨天面试的时候,面试官问我了个平平淡淡的问题–>“聊聊Linux中进程和线程”; 相比大家不管是在考试还是面试中或多或少都遇到过这个问题&…...

【mmdeploy部署系列】使用Tensorrt加速部署mmpose人体姿态库
【mmdeploy部署系列】使用Tensorrt加速部署mmpose人体姿态库0.引言1.安装mmcv2.使用mmpose(1)安装mmpose(2)运行mmpose3.使用mmdeploy(1)安装ppl.cv(2)编译安装mmdeploy(…...

IDEA 每次新建工程都要重新配置 Maven 解决方案
IDEA 每次新建工程都要重新配置 Maven 解决方案 IDEA 每次新建工程都要重新配置 Maven,是一件相当浪费时间的事情。这是因为在创建一个项目后,在 File -> Settings -> Build,Execution,Deployment -> Build Tools -> Maven下配置了 Maven h…...

【C++修炼之路】25.哈希应用--布隆过滤器
每一个不曾起舞的日子都是对生命的辜负 布隆过滤器前言一.布隆过滤器提出二.布隆过滤器概念三. 布隆过滤器的操作3.1 布隆过滤器的插入3.2 布隆过滤器的查找3.3 布隆过滤器的删除四.布隆过滤器的代码4.1 HashFunc的仿函数参考4.2 BloomFilter.h五.布隆过滤器的优缺点六.布隆过滤…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...