【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五.布隆过滤器的优缺点六.布隆过滤…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...

如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...