贪心算法（一）-训练1-1
区间覆盖问题（最少点覆盖）
【描述】给定多个区间，用最少的点覆盖所有区间。
【输入描述】区间数n，随后2n个整数（左端点 右端点，n组）
【输出描述】最少需要的点数
【样例输入】
3
1 3
2 5
4 6
【样例输出】
2
#include<iostream>#include<algorithm>usingnamespacestd;structInterval{intleft,right;};boolcompare(Interval a,Interval b){returna.right<b.right;// 按右端点排序}intminPoints(Interval arr[],intn){sort(arr,arr+n,compare);intpoints=0,lastPoint=-1;for(inti=0;i<n;i++){if(arr[i].left>lastPoint){points++;lastPoint=arr[i].right;// 选当前区间的右端点}}returnpoints;}intmain(){intn;cin>>n;Interval arr[n];for(inti=0;i<n;i++){cin>>arr[i].left>>arr[i].right;}cout<<minPoints(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个整数（各堆数量）
【输出描述】最少移动次数
【样例输入】
3
3 1 2
【样例输出】
1
#include<iostream>usingnamespacestd;intmain(){intn;cin>>n;inta[n];intsum=0;// 输入并计算总和for(inti=0;i<n;i++){cin>>a[i];sum+=a[i];}intavg=sum/n;// 计算平均值intmoves=0;// 移动次数intprefix=0;// 前缀和// 遍历计算移动次数for(inti=0;i<n;i++){prefix+=a[i]-avg;// 计算累计差值if(i!=n-1&&prefix!=0){moves++;// 每次传递差值产生一次移动}}cout<<moves<<endl;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
#include<iostream>usingnamespacestd;intmaxSoda(intn){inttotal=0,empty=n;while(empty>=3){intnewSoda=empty/3;total+=newSoda;empty=empty%3+newSoda;// 剩余空瓶 + 新喝的空瓶}returntotal;}intmain(){intn;cin>>n;cout<<maxSoda(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
纪念品分组
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
【输入】共 n+2行：（0<=n<=50）
第一行包括一个整数 w，为每组纪念品价格之和的上限。
第二行为一个整数 n，表示购来的纪念品的总件数。
第 3～n+2行每行包含一个正整数 Pi表示所对应纪念品的价格。
【输出】
一个整数，即最少的分组数目。
【输入样例】
100
9
90
20
20
30
50
60
70
80
90
【输出样例】
6
#include<iostream>#include<algorithm>usingnamespacestd;constintN=55;inta[N],w,n,ans;intmain(){cin>>w>>n;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);//从小到大排序inti=1,j=n;// i左指针，j右指针while(i<=j){if(a[i]+a[j]<=w){//i,j之和不超w，两个组合打包ans++,i++,j--;}elseans++,j--;// 否则，（大的那个）j单独打包}cout<<ans;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个整数（物品重量）
【输出描述】最多能装的物品数量
【样例输入】
10
3
4 2 3
【样例输出】
3
#include<iostream>#include<algorithm>usingnamespacestd;intmain(){intC,n;cin>>C>>n;intw[100];for(inti=0;i<n;i++){cin>>w[i];}sort(w,w+n);// 按重量升序排序inttotal=0,count=0;for(inti=0;i<n;i++){if(total+w[i]<=C){total+=w[i];count++;}elsebreak;}cout<<count<<endl;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 */
