贪心算法的应用实例

贪心算法的应用实例 贪心算法的应用实例 例2(排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，(0<i<=n),请求出一种排列次序，使每个人排队等候时间总和最小。 输入数据:第1行一个正整数n(你<=10000》，第2行有n 个不超过 1000的正整数ti. 输出 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 :n个人排队时间最小总和。 输入输出样例 输入:4 5 10 8 7 输出: 67 【算法分析】 本题贪心算法:n个人时间从小到大排序，就是这n个人最佳排队 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。求部分和的和即为所求。 反证法证明:假设有最优解序列:s1,s2„sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)>0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2„sn依次最小。 例3(:数列极差问题 【题目描述】 在黑板上写了N个正整数做成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。 编程任务:对于给定的数列，编程计算出极差M。 输入输出样例: 输入: 4 2 1 4 3 输出: 13 【算法分析】 当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。 下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论:假设经(,,3)次变换后得到,个数:a ,b , max,(max,?,?,)，其中max,是(,,,)个数经(,,,)次,变换后所得的最大值，此时有两种求值方式，设其所求值分别为 z1，z2，则有:z1,(,×,，,)×max,，,，z2,(,×max,，,)×,+,所以z1,z2,max,,,?,若经(,,,)次变换后所得的,个数为:,，,， 1 ,(,?,?,)且,不为(,,,)次变换后的最大值，即,,max,则此时所求得的最大值为: z3,(,×,+,)×,+,此时z1,z3,(,+,,)(max,,,),, 所以此时不为最优解。 所以若使第,(,?,?,,,)次变换后所得值最大，必使(,,,)次变换后所得值最大(符合贪心策略的特点2)，在进行第,次变换时，只需取在进行(,,,)次变换后所得数列中的两最小数,，？施加,操作:,?,×？+1，？??即可(符合贪心策略特点1)，因此此题可用贪心策略求解。在求,in时，我们只需在每次变换的数列中找到两个最大数,，？施加作用 ,:,?,×？+,，？?-?即可(原理同上。 这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。 例4(整数区间range.cpp 【题目描述】 我们定义一个整数区间[a,b],a,b是一个从a开始至b 结束的连续整数的集合。编一个程序，对给定的 n个区间，找出满足下述条件的所含元素个数最少的集合中元素的个数:对于所给定的每一个区间，都至少有两个不同的整数属于该集合。(1<=n<=10000, 0<=a<=b<=1000) 输入输出格式: 输入:第一行一个正整数n，接下来有n行，每行给定一个区间的a,b值 输出:一个正整数，即满足条件的集合所包含的最少元素个数 输入输出样例 输入: 输出: 4 4 3 6 2 4 0 2 4 7 【算法分析】 本题数据规模较大，用搜索做会超时，而动态规划无从下手。考虑贪心算法。题目意思是要找一个集合，该集合中的数的个数既要少又要和所给定的所有区间有交集。(每个区间至少有两个该集合中的数)。我们可以从所给的区间中选数，为了选尽量少的数，应该使所选的数和更多的区间有交集这就是贪心的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。一开始将所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检查，看所选出的数与所查看的区间有无交集，有两个则跳过，只有一个数相交，就从当前区间中选出最大的一个数(即右端点)，若无交集，则从当前区间选出两个数，就(右端点，右端点-1)，直至最后一个区间。 #include <iostream>//整数区间问题 using namespace std; struct prince{ int left,right;//区间左右端点 }a[10000]; int n; int result;//存放结果中的数 int cmp(const void *a,const void *b){ return (*(prince *)a).right-(*(prince *)b).right; 2 } int work(){ qsort(a+1,n,sizeof(a[0]),cmp);//按区间右端点由小到大排序 int i,j,k; int a1,a2; a1=a[1].right-1;a2=a[1].right;result=2; for(i=2;i<=n;i++) { if(a[i].left<=a1&& a[i].right>=a2)continue;//完全包含 if (a[i].left>a2 )//完全不包含 {a1=a[i].right-1;a2=a[i].right;result=result+2;} if (a[i].left>a1 && a[i].right>a2 && a[i].left<=a2) {a1=a2;a2=a[i].right;result++;}//只包含一个 } return result; } int main(){ freopen("range6.in","r",stdin); freopen("range6.out","w",stdout); cin>>n; int i; for(i=1;i<=n;i++) cin>>a[i].left>>a[i].right; cout<<work()<<endl; return 0; } 例5(骆驼商队Camel Trading 【题目描述】 在一片古老的大地上，虽然商业已经非常繁荣，但是那里的人们仍然延续着古老的交易方式。他们牵着骆驼在城市之间往来奔波，贩运成批的商品，换来一袋袋的金币。 这片大陆上有N个城市，编号为1„„N。在一些城市之间有路可通，有路就有商队。但是在不同的城市之间经商所得的收益不同，在下面的这个N=4的例子中，在城市1和城市2之间进行一次交易可以获得40枚金币，在城市2和3之间交易一次可以获得50枚金币，等等。 在任意两个城市之间，这样的交易只能进行一次。因为你第二次贩运你的商品时，人们对它们就不会感兴趣了。 现在你只身来到这个大陆上，用有限的资金在每个城市中购买了一支商队。你需要想办法让你的这N支商队给你带来最大的经济收益。 3 任务说明 给出这个大陆的地图和每两个城市之间的贸易值(如果这两个城市之间有路可通的话)，你需要指挥你的N支商队进行一次经商，使得这N支商队在这次经商中获得的总收益最大。注意:你的每支商队只能进行一次交易，即它们只能从它们所在的城市到达一个相邻的城市。当然，它们也可以不进行任何交易。 输入数据 输入文件的第一行有两个整数N()、M()，分别表示这个大陆上的城市数和道路数。 接下来有M行，每行包括三个整数i、j(且)、，表示一条道路的信息。其中i和j表示这条路在城市i和城市j之间，v表示沿着这条路进行一次交易所得的收益。i和j的顺序是无关的，并且任意两个城市之间最多存在一条路。 输出数据 你的输出文件应该2行，第1行包含N个整数。其中第k个整数表示你在城市k中的商队将要前往哪个城市进行交易(如果这支商队进行交易的话)或者为0(如果这支商队不进行任何交易)。第2行输出最大收益值。 输入输出样例 【算法分析】 本题转化成模型就是:在一个无向图中，对于每个点，取一条和它相关联的边(如果这样的边存在的话)，使得取出来的所有边的权和最大。 首先，如果这个图是不连通的，那么它的各个连通分量之间是没有任何联系的。对这些连通分量中的问题可以分别独立地解决，合并起来就是整个问题的解。所以我们在下面的讨论中假定图是连通的。 直观地考虑，如果图中存在度为1的点，那么就把这一点上的唯一的一条边分配给这个点(将某条边“分配”给某个点的含义是:将这条边作为和这一点相关联的边取出来，同时这一点就失效了，因为和它相关联的其他边都不能再取了)。如果不存在这样的点，那么此时有两种情况:一种是边数等于点数，那么这个图就是一个环，这时可以取出图中所有的边;一种是边数大于点数，那么就可以把这个图中权最小的一条边直接删去，因为这条边“显然”不会被取到的。 依据这样一个直观思想，本题可以用贪心法来解决。 贪心算法(用于连通图): 1、如果图中只有一个点，直接结束算法。 2、如果图中存在度为1的点，执行3;否则转4。 3、任意找一个度为1的点v，将v上的唯一一条边分配给它。转2。 4、如果图中的边数等于点数，执行5;否则转6。 5、设图中的点数(也就是边数)为n。任取一条边e1，将它分配给它的两个端点中的任 意 4 一个v1;然后将v1上的另一条边e2分配给e2的另一个端点v2;将v2上的另一条边e3分配给e3的另一个端点v3;„„如此重复直到将en分配给vn，即图中所有的边都已分配，结束算法。 6、将图中权最小的边不分配而直接删去。如果此时图仍然连通，则转2;否则对这个图的两个连通分量分别执行本算法。 例6(数字游戏 【题目描述】 小W发明了一个游戏，他在黑板上写出一行数字a1，a2，„an,然后给你m个回合的机会，每个回合你可以从中选一个数擦除它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦除的数字之和就是你得到的分数。 编程帮小W算算，对于每个给出的an和bn序列，可以得到的最大得分是多少, 数据输入: 由文件game. in提供输入数据。文件的第1 行一个整数n(1?n?200)，表示数字的个数;第二行一个整数m(1?m?n)，表示回合数;接下来一行有n个不超过10000的正整数，a1，a2，„an，表示原始数字;最后一行有n个不超过500的正整数，b1，b2，„bn，表示每回合每个数字递减的值。 结果输出: 程序运行结束时，将计算结果输出到文件game. out 中。一个整数，表示最大可能的得分。 输入文件示例 输入: 3 3 10 20 30 4 5 6 输出: 47 【算法分析】 本题上面一排数是作为被减数的，若对被减数采用贪心算法不一定能得到全局最优解。因为被减数小减数大，其差小会导致最大得分少。先运用贪心的思想对第二排减数进行从大到小排序，再运用动态规划思想递推求解。 #include<iostream>//数字游戏 using namespace std; struct XX {int a,b; }a[201]; int n,m,f[2][201],i,j; int comp(const void *a,const void *b) { return(*(XX*)b).b-(*(XX*)a).b; } int main() 5 { freopen ("game10.in","r",stdin); freopen ("game.out","w",stdout); memset(f,0,sizeof(f)); cin>>n>>m; for (i=1;i<=n;i++) cin>>a[i].a>>a[i].b; qsort(a+1,n,sizeof(a[0]),comp); for (i=1;i<=n;i++) for (j=1;j<=min(i,m);j++) f[i%2][j]=max(f[(i-1)%2][j],f[(i-1)%2][j-1]+a[i].a-\ a[i].b*(j-1)); cout<<f[n%2][m]<<endl; return 0; } 例7(开会问题 某公司的会议日益增多，以至于全公司唯一的会议室都不够用了。现在给出这段时期的会议时间表，要求你失单适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议最少。 输入格式:第1行n,表示有n 个会议。接下来有n行，每行两个数，si，fi表示会议i的起止时间。 输出格式:仅1行，删除的最少会议数d. N<=500,si,fi为整型数 注意:会议(1，3)和会议(3，5)是不冲突的，但和会议(2，5)是冲突的。 【算法分析】 题目要求删除最少的会议，使得剩余的会议在时间上不互相冲突，这实际上是要求安排最多的在时间上不冲突的会议。由于我们的目标是尽可能多地安排会议，而不管安排了那些会议，所以可采用以下贪心方法:首先将所有会议按结束时间从小到大排序，每次总是安排结束时间早的会议，这样不仅安排了一个会议，同时又为剩余的会议留下尽可能的时间。 例8(智力大冲浪 【题目描述】 小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。接下来主持人宣布比赛规则:首先，比赛时间分为n个时段(n<=500),它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(i<=ti<=n)。如果一个游戏每能在规定期限完成，则要从奖励费m元中扣去一部分钱wi，wi 为自然数，不同的游戏扣去的钱数不同。当然每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整数段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。问小伟最多能得到多少钱, 输入:第1行为m，表示一开始奖励给每个参赛者的钱数 第2行为n表示有n个小游戏。 第3行有n个数，分别表示n个游戏规定完成的期限 第4行有n个数，分别表示n个游戏不能在规定期限完成的扣款数 输出:仅一个数，表示小伟能赢得最多的钱数。 样例: 6 输入: 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 输出: 9950 【算法分析】 因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢,应该放在第k个时段，因为放在1,k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的. 本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。当扫描到第n个时段，发现里面所分配任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1,n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺， 例9(合并果子(fruit.pas)。 【题目描述】 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如，有3种果子，数目依次为1、2、9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力15=3+12。可以证明15为最小的体力耗费值。 【输入】 输入文件fruit.in包括两行。第一行是一个整数n(1?n?10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1?ai?20000)是第i种果子的数目。 【输出】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。 【样例输入】 3 1 2 9 【样例输出】 15 7 【数据规模】 对于30%的数据，保证有n?1000; 对于50%的数据，保证有n?5000; 对于全部的数据，保证有n?10000。 【算法分析】 此题用贪心法。先将果子数排序，取其中最小的两堆合并，得到一个新堆;再排序，再取其中最小的两堆合并„„直到只剩一堆。为尽快出解，排序的速度显得格外重要，可用堆排序算法。 例10( 建筑抢修(repair.pas)。 【题目描述】 小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏。经过了一场激烈的战斗，T部落消灭了所有Z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。 现在的情况是:T部落基地里只有一个修理工人。虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之T1,T2,maxlongint 【样例输入】 4 100 200 200 1300 1000 1250 2000 3200 【样例输出】 3 【算法分析】 贪心 O(N Log N) + 高级数据结构。很容易想到动态规划。按截止时间排序，维护队列q，如果能插入就插入，如不能插入，就把一个花费时间最大的替换下来 贪心算法和贪心思想看似简单，真正完全掌握要下一番功夫。和任何优秀算法一样，贪心算法也有它的局限性，用不对会丢很多解，用得好，在编程中能起到事半功倍的效果。 有不对之处请指正，谢谢大家～ 8