C++贪心算法一（练习题）

贪心算法一-训练1-1区间覆盖问题最少点覆盖【描述】给定多个区间用最少的点覆盖所有区间。【输入描述】区间数n随后2n个整数左端点 右端点n组【输出描述】最少需要的点数【样例输入】31 32 54 6【样例输出】2#includeiostream#includealgorithmusingnamespacestd;structInterval{intleft,right;};boolcompare(Interval a,Interval b){returna.rightb.right;// 按右端点排序}intminPoints(Interval arr[],intn){sort(arr,arrn,compare);intpoints0,lastPoint-1;for(inti0;in;i){if(arr[i].leftlastPoint){points;lastPointarr[i].right;// 选当前区间的右端点}}returnpoints;}intmain(){intn;cinn;Interval arr[n];for(inti0;in;i){cinarr[i].leftarr[i].right;}coutminPoints(arr,n)endl;return0;}/* 【输入用例2】 3 1 3 2 5 4 6 【输出用例2】 2 【输入用例3】 3 0 0 0 1 1 2 【输出用例3】 2 【输入用例4】 5 1 2 3 4 5 6 7 8 9 10 【输出用例4】 5 【输入用例5】 4 1 5 2 5 3 5 4 5 【输出用例5】 1 【输入用例6】 1 100 200 【输出用例6】 1 */贪心算法一-训练1-2均分纸牌问题最少移动次数【描述】n堆纸牌每次移动随意张到相邻堆求使各堆数量相同的最少移动次数。【输入描述】纸牌数n随后n个整数各堆数量【输出描述】最少移动次数【样例输入】33 1 2【样例输出】1#includeiostreamusingnamespacestd;intmain(){intn;cinn;inta[n];intsum0;// 输入并计算总和for(inti0;in;i){cina[i];suma[i];}intavgsum/n;// 计算平均值intmoves0;// 移动次数intprefix0;// 前缀和// 遍历计算移动次数for(inti0;in;i){prefixa[i]-avg;// 计算累计差值if(i!n-1prefix!0){moves;// 每次传递差值产生一次移动}}coutmovesendl;return0;}/* 【输入用例2】 3 3 1 2 【输出用例2】 1 【输入用例3】 5 6 6 6 6 6 【输出用例3】 0 【输入用例4】 2 6 8 【输出用例4】 1 【输入用例5】 4 6 8 8 6 【输出用例5】 2 【输入用例6】 6 6 12 18 24 30 36 42 【输出用例6】 5 */贪心算法一-训练1-3汽水瓶兑换问题【描述】每3个空瓶换1瓶汽水n个空瓶最多能喝多少瓶【输入描述】空瓶数n【输出描述】最多能喝的汽水数【样例输入】21【样例输出】10#includeiostreamusingnamespacestd;intmaxSoda(intn){inttotal0,emptyn;while(empty3){intnewSodaempty/3;totalnewSoda;emptyempty%3newSoda;// 剩余空瓶 新喝的空瓶}returntotal;}intmain(){intn;cinn;coutmaxSoda(n)endl;return0;}/* 【输入用例2】 7 【输出用例2】 3 【输入用例3】 15 【输出用例3】 7 【输入用例4】 45 【输出用例4】 22 【输入用例5】 99 【输出用例5】 49 【输入用例6】 0 【输出用例6】 0 */贪心算法一-训练2-1纪念品分组元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。【输入】共 n2行0n50第一行包括一个整数 w为每组纪念品价格之和的上限。第二行为一个整数 n表示购来的纪念品的总件数。第 3n2行每行包含一个正整数 Pi表示所对应纪念品的价格。【输出】一个整数即最少的分组数目。【输入样例】1009902020305060708090【输出样例】6#includeiostream#includealgorithmusingnamespacestd;constintN55;inta[N],w,n,ans;intmain(){cinwn;for(inti1;in;i)cina[i];sort(a1,an1);//从小到大排序inti1,jn;// i左指针j右指针while(ij){if(a[i]a[j]w){//i,j之和不超w两个组合打包ans,i,j--;}elseans,j--;// 否则大的那个j单独打包}coutans;return0;}/* 【输入用例2】 10 4 1 2 3 4 【输出用例2】 2 【输入用例3】 5 3 1 2 5 【输出用例3】 2 【输入用例4】 4 4 1 1 1 1 【输出用例4】 2 【输入用例5】 3 3 2 2 2 【输出用例5】 3 【输入用例6】 6 5 1 2 3 4 5 【输出用例6】 3 */贪心算法一-训练2-2最优装载问题重量优先【描述】小王家有一条商务船靠每天幸苦运货赚取学编程的费用有一天他突发奇想船的最大载重为C有n个物品重量分别为w[0…n-1]我每次最多能装多少个物品呢【输入描述】C载重n物品数随后n个整数物品重量【输出描述】最多能装的物品数量【样例输入】1034 2 3【样例输出】3#includeiostream#includealgorithmusingnamespacestd;intmain(){intC,n;cinCn;intw[100];for(inti0;in;i){cinw[i];}sort(w,wn);// 按重量升序排序inttotal0,count0;for(inti0;in;i){if(totalw[i]C){totalw[i];count;}elsebreak;}coutcountendl;return0;}/* 【输入用例2】 10 12 1 1 1 1 1 1 1 1 1 1 1 1 【输出用例2】 10 【输入用例3】 10 9 1 2 3 4 5 6 7 8 9 10 【输出用例3】 4 【输入用例4】 100 6 12 56 48 32 11 2 【输出用例4】 4 【输入用例5】 200 10 12 23 54 1 2 56 3 96 62 70 【输出用例5】 7 【输入用例6】 500 13 10 20 30 40 50 60 70 80 90 100 110 120 130 【输出用例6】 9 */