贪心1实验题目减肥的小K1题目描述小K没事干他要搬砖头为了达到较好的减肥效果教练规定的方式很特别每一次小K可以把两堆砖头合并到一起消耗的体力等于两堆砖头的重量之和。经过 n-1次合并后 就只剩下一堆了。小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和。小K为了偷懒希望耗费的体力最小。例如有 3堆砖头数目依次为 1、2、9 。可以先将 1 、 2 堆合并新堆数目为3 耗费体力为 3 。接着将新堆与原先的第三堆合并又得到新的堆数目为 12 耗费体力为12 。所以总共耗费体力 31215。可以证明 15为最小的体力耗费值。输入要求共两行。第一行是一个整数 n(1≤n≤1000) 表示砖头堆数。第二行n个整数每个整数表示每堆砖头的砖头块数。输出要求一个整数也就是最小的体力耗费值。实验代码及注释:1234567891011121314151617181920212223#include bits/stdc.husingnamespacestd;intmain() {intn, a[1000], sum 0, i;cin n;for(i 0; i n; i){cin a[i];}sort(a, a n);for(i 0; i n - 1; i) {inttemp a[i 1] a[i];//记录前两个最小的值intk i 2;//k为第三个的下标while(a[k] temp k n) {//比较第三个和前两个的和若第三个比前两个要小a[k - 1] a[k];//前移k;}a[k - 1] temp;sum temp;}cout sum endl;return0;}算法分析与知识点本题主要运用贪心的思想每次都在全部砖头中找到重量最轻的两堆进行合并以达到最节约体力的目的。因此要先对全部砖头按重量进行排序需要注意的是再合并完两堆砖头后需要对后续砖头堆进行重新排序第一次WA就是因为没有对后续砖头堆进行重新排序。实验题目最小跳数题目描述给定一个非负整数数组假定你的初始位置为数组第一个位置。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标位置并且使用最少的跳跃次数。输入要求输入一组非负整数数组数组长度不超过500。输出要求最少经过几次跳跃可以到达最后一个位置。实验代码及注释:1234567891011121314151617181920212223#include bits/stdc.husingnamespacestd;intmain() {intn 0, a[501];while(cin a[n]);n n - 1;// maxPos 记录当前最远能到哪里// step 记录当前进行了几跳// end 记录了当前最远能到哪里的边界intmaxPos 0, end 0, step 0;for(inti 0;i n - 1;i) {if(maxPos i) {//判断能否继续探索maxPos max(maxPos, i a[i]);if(i end) {// 到达边界更新跳数end maxPos;step;}}}cout step endl;return0;}算法分析与知识点本题主要运用贪心的思想在具体的实现中我们维护当前能够到达的最大下标位置记为边界。我们从左到右遍历数组到达边界时更新边界并将跳跃次数增加 1。在遍历数组时我们不访问最后一个元素这是因为在访问最后一个元素之前我们的边界一定大于等于最后一个位置否则就无法跳到最后一个位置了。如果访问最后一个元素在边界正好为最后一个位置的情况下我们会增加一次「不必要的跳跃次数」因此我们不必访问最后一个元素。实验题目排队接水题目描述夏天到了又到了用水高峰期偏巧小区的水管出了点问题消防车赶紧给小区送了一车水过来。小区居民们纷纷拿出自家装水的容器有的是个大塑料瓶有的是茶水壶有的是小塑料桶哈哈什么样的都有:)。现在有n个人在一个水龙头前排队接水假设每个人接水的时间分别为Ti请编程找出这n个人排队的一种顺序使得这n个人的平均等待时间最小。输入要求输入有多组测试数据每组测试数据共两行第一行为一个整数n表示有n个人第二行分别表示第1个人到第n个人每人的接水时间T1T2,…Tn。输出要求输出文件有两行第一行为一种排队顺序即编号从1到n的n个人的一种排序方式第二行为这种排序方案下的平均等待时间输出结果精确到小数点后两位。实验代码及注释:123456789101112131415161718192021222324252627282930#include bits/stdc.husingnamespacestd;structperson// 定义居民结构体记录到来顺序及接水时间{intid,time;};person p[1000];boolcmp(person p1, person p2) {// 自定义结构体排序方法returnp1.time p2.time;}intmain() {intn;while(cin n) {for(inti 0;i n;i) {p[i].id i;cin p[i].time;}sort(p, p n, cmp);// 按接水时间升序doubleans 0;for(inti 0;i n - 1;i) {cout p[i].id 1 ;ans (n - 1 - i) * p[i].time;}cout p[n - 1].id 1 endl;printf(%.2f\n, ans / n);}return0;}算法分析与知识点本题主要运用贪心的思想共有n名居民他们所需的接水时间分别为 设他们的排队顺序为 可得出总共等待时间为由以上公式可得要使得总的排队等待时间最短就要按接水所需时间从小到大的顺序老排队接水。贪心-堂练实验题目 区间问题1题目描述给出n个区间的起点和终点求最少使用其中多少个区间可以将所有区间所在的区域完全覆盖。测试的数据确保这1点。输入要求第1行一个整数n表示n个区间第2行开始n行每行2个整数表示一个区间范围。类似[1,4] [5,6]被认为是覆盖了[1,6]。输出要求从起点开始按区间先后顺序输出选中的区间。所选的区间应尽可能向终点扩展。实验代码及注释:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include bits/stdc.husingnamespacestd;structpart//区间两端{intstar1, end1;};boolcmp(part s1, part s2) {// 自定义排序方式1、开始点升序2、结束点升序if(s1.star1 s2.star1)returntrue;elseif(s1.star1 s2.star1 s1.end1 s2.end1)returntrue;elsereturnfalse;}intmain(){part a[100];//全部待选区间part r[100];//在a中选好的数放入r中intn, index 0, i;cin n;for(i 0; i n; i) {cin a[i].star1 a[i].end1;}sort(a, a n, cmp);intright a[0].star1 - 1;intend a[n - 1].end1;// 待覆盖区间最远处for(i 0; i n - 1; ){intmaRight a[i].end1, maIndex i;while(a[i].star1 right 1 i n) {// 寻找最远子区间if(a[i].end1 maRight) {maRight a[i].end1;maIndex i;}i;//比较完数组往后移}right maRight;r[index] a[maIndex];i maIndex;if(right end)break;}for(i 0; i index; i) {cout r[i].star1 r[i].end1 endl;}return0;}算法分析与知识点思路设置一个a[]数组保存原始的数据设置一个人r[]数组保存被选的区间数据。先按1、开始点升序2、结束点升序将数据排序。为了使覆盖总区间的所需的子区间数最少就要选出一系列覆盖范围最广的子区间。方式描述如下所示初始令所能到达的范围为 然后选出一个子区间让这个范围尽可能向区间终点靠即找到符合条件 的最远子区间。实验题目种树题目描述一条街的一边有几座房子。因为环保原因居民想要在路边种些树路边的地区被分割成块并被编号成1…N每个部分为一个单位尺寸大小并最多可种一棵树每个居民想在门前种些树并指定了三个号码B,E,T这三个数表示该居民想在B和E之间最少种T棵树。当然B≤E,居民必须记住在指定区不能种多于区域地块数的树所以T≤E-Bl。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。输入要求第一行包含数据N区域的个数第二行包含H房子的数目下面的H行描述居民们的需要:B E T。输出要求输出能满足所有要求的最少的树的数。实验代码及注释:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include bits/stdc.husingnamespacestd;intn, m, k, ans;structnode// 保存要求数据{intb, e, t;}a[5005];boolused[30005];// 记录该位置是否种过树boolcmp(constnode a,constnode b)// 自定义排序方式{returna.e b.e;}intmain(){cin n m;for(inti 0;i m;i)// 输入数据{cin a[i].b a[i].e a[i].t;}sort(a, a m, cmp);memset(used, 0,sizeof(used));//初始化每个位置都没种过树ans 0;// 记录所需树的数量for(inti 0;i m;i){k 0;for(intj a[i].b;j a[i].e;j)// 求在该要求区间内已经种了多少树{if(used[j]) k;}if(k a[i].t)// 未达到要求continue;k a[i].t - k;// 还要种的数量for(intj a[i].e;j a[i].b;j--){if(used[j] false)// 寻找没种过的位置{used[j] true;//种树ans;k--;}if(k 0)break;}}cout ans endl;return0;}算法分析与知识点本题采用贪心算法的思想要使所需的总树苗数量最小就要让一个区间的树苗将可能的能满足更多的用户要求。这里采用让后面的居民尽可能为前面的居民着想即在满足自己要求的前提下把树尽可能地往前面的位置种这样可以让居民的要求重叠的范围更多从而达到使用最少的树苗满足所有居民的要求。为了达到目的我们需要先将居民按提出要求的开始区间点排序然后从后往前尽可能地为前面地居民考虑。考虑满足第i个居民方式要先考虑满足第i1个居民的要求后里自己的要求还差多少然后由于为第i-1个居民着想的目的将未满足要求的树苗种在第i个居民要求区间的前面。实验题目智力大冲题目描述小伟报名参加中央电视台的智力大冲浪节目本次挑战赛吸引了众多参赛者主持人为了表彰大家的勇气先奖励每个参赛者m元。先不要太高兴因为这些钱还不一定都是你的接下来主持人宣布了比赛规则首先比赛时间分为n个时段(n≤500),它又给出了很多小游戏每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成则要从奖励费m元中扣去一部分钱wiwi为自然数不同的游戏扣去的钱是不一样的。当然每个游戏本身都很简单保证每个参赛者都能在一个时段内完成而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者小伟很想赢得冠军当然更想赢取最多的钱注意:比赛绝对不会让参赛者赔钱输入要求输入文共4行。第1行为m表示一开始奖励给每位参赛者的钱第2行为n表示有n个小游戏第3行有n个数分别表示游戏1到n的规定完成期限第4行有n个数分别表示游戏1到n不能在规定期限前完成的扣款数。输出要求输出仅1行表示小伟能赢取最多的钱。实验代码及注释:1234567891011121314151617181920212223242526272829303132333435#include bits/stdc.husingnamespacestd;constintN 510;intn, m, f[N];structnode {intt, w;}a[N];intcmp(node x, node y) {returnx.w y.w; }// 自定义排序方式voidwork(){sort(a 1, a 1 n, cmp);for(inti 1;i n;i){boolpd false;// 判断该游戏是否被完成for(intj a[i].t;j 1;j--){if(f[j] 0)//可以安排这个游戏{f[j] 1;pd true;break;}}if(pd false) m - a[i].w;}}intmain(){cin m n;for(inti 1;i n;i) cin a[i].t;for(inti 1;i n;i) cin a[i].w;work();cout m endl;return0;}算法分析与知识点本题采用贪心算法的思想首先将所有游戏按其价值从高到低排序。一个游戏只要在规定期限完成之前完成就不会被扣除奖励为了让一个游戏尽可能不影响其他游戏我们让其在自己的规定期限内尽可能地往后靠。我们从奖励价值最高的游戏开始考虑将所有游戏考虑完成后就可以得到的所获得的奖励最大值。实验题目删除数字II题目描述在给定的n个数字的数字串m中删除其中k(k n)个数字后剩下的数字按原次序组成一个新的整数。请确定删除方案使得剩下的数字组成的新整数最小。(1kn240)输入要求输入有一行先输入数字串m再输入k如描述所示。保证数字串m没有前导0。输出要求输出有两行第一行按顺序输出从左到右删除的k个数字用空格隔开。第一行里的输出顺序是按照被删除数字在原数中的顺序排列的而不是按照删除的顺序排列的