专业律所网站建设,企业官网维护,ae模板网站推荐,开发技术网站开发技术目录
题目
输入格式
输出格式
样例
提示
思路
代码 题目
单点时限: 2.0 sec
内存限制: 256 MB
oxx 与 xjj 终于到了 Xiamen#xff0c;他们第一件事就是去吃当地著名的特产椰子饼。
他们共买了 n 盒礼盒#xff0c;第 i 盒含 ai 块椰子饼。oxx 与 xjj 约定让 oxx …目录
题目
输入格式
输出格式
样例
提示
思路
代码 题目
单点时限: 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。
如果上述题意让你感到很困惑的话我们要求的是 Sa1,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 2output
Yes
1
1input
7
4 5 4 5 4 5 4output
Yes
3
2 4 6提示
样例 2在 oxx 挑了 5、5、5 这三个之后总和 15 不超过 xjj 拿到的 4、4、4、4 的总和 16而且无论 xjj 偷吃了哪个反正都是 415 总大于等于 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 MAX1e610;
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;cinn;// 输入饼干数for(int i0;in;i) {cinvalue[i];id[i]i;} // 根据饼干盒中饼干的数量对饼干盒id进行倒序排序sort(id,idn,cmp);ll x0,y0;// 两堆饼干盒的饼干数量setint xId,yId;// 两堆饼干盒的id们 // 不断地把较大的饼干盒分给较小的堆for(int i0;in;i) {if(xy) {// x是小堆时第i大的饼干盒就给它 xvalue[id[i]];xId.insert(id[i]1);// 加一是因为饼干盒的id是从1开始算的 } else {// y是小堆时yvalue[id[i]];yId.insert(id[i]1); } } // 一定是有符合要求的分配的coutYesendl;// 较小的堆是oxx的if(xy) {coutxId.size()endl;for(int s:xId) couts ;} else {coutyId.size()endl;for(int s:yId) couts ;}return 0;
}
