【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五.布隆过滤器的优缺点六.布隆过滤…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...