贪心算法详解C++版

【例3・1]删数问j【问题描述】键盘输入一个高精度的正整数n5<=240位)，去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数字组成的数最小。输入：NS输出：最后剩下的最小数。【样例输入】1785434【样例输出】13【题解】由于正整数n的有效位数为240位，所以很自然地采用字符串类型存储n。那么如何解决哪s位被删呢？是不是最大的s个数字呢？为了尽可能的逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下数最小的数字删去。即按高位到低位的顺序搜索，若各位数字递增，则删去最后一个数字；否则删去第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重灾以上过程s次为止，剩下的字串便是问题的解了。【标程】#iiiclude<iostreain>#iiiclude<cstdio>#iiiclude<cstrmg>usingnamespacestd;chara[100001];hitmam()(mtgets(a);cm»n;l=stilen(a);for(j=0j<l-lJ++)if(a[j]>a[j+l])fbr(k=j;k<l-l;k++)a[k]=a[k+1];break;)1-;}或a[i]!=O)(k=i;break;)}for(j=ij<=l-lJ++)cout«a[j]；cout«endl;retiim0;}【例3-2]取数游戏【问题描述】给出211（11<=100）个自然数（数小于等于30000）。游戏双方分别为A方（计算机）和B方（对弈的人）。只允许从数列两头取数。A先取，然后双方一次轮流取数。取完时，谁取得的数字总和最大为取胜方；若双方和相同，属于A胜。试问A方可否有必胜的策略？输入：479364253RRRR键盘输入n以及2*n个自然数。输出：352463973619共3n+2行，其中前3*n行为游戏过程。每三行分别为A方所取的数和B方所取的数，及B方取数前应给与适当的提示，让游戏者选取那一头的数（LR—左端或右端）。最后两行分别为A方取数之和与B方取数之和。【标程】progiainho;varn.i,j,sa,sb,lp,ip,t:longint;ch:char;a:anay[1..200]oflongint;begmreadlii(n);fori:=lto2*ndoread(a[i]);sa:=0;sb:=O;fori:=ltondobeginsa:=sa+a[2*i-l];sb:=sb+a[2*i];end;ifsa>=sbthenj:=lelsebeginJ：=o；t:=sa;sa:=sb;sb:=t;end;lp:=l;ip:=2*n;fori:=ltondobeginif(j=l)aiid(lpmod2=1)or((j=0)and(lpmod2=0))thenbeginwriteln(a[lp]);mc(lp);endelsebeginwriteln(a[rp]);dec(rp);end;wiite(B=LR?);[叩uatreadlii(ch);ifch='L'thenbeginwriteln(a[lp]);mc(lp);end;ifch='R'thenbeginwritelii(a[rp]);dec(rp);end;until(ch='U)or(ch=R);end;wnteln(sa);wnteln(sb);end.【例3・3】活动选择【问题描述】假设有一个需要使用某以资源的n个活动组成的集合S,S={1,…，n}。该资源一次只能被一个活动占用，每一个活动有一个开始时间历和结束时间ei（bi〈=ei）。若b〉=ej或bj>=ei,则活动1和活动J兼容。你的任务是：选择由相互兼容的活动组成的最大集合。输入：输入文件名为：act.m,共n+1行，其中第一行为n,第二行到第n+1行表示n各活动的开始时间和结束时间（中间用用空格隔开），格式为：nblelbnen输出：输出文件名为：act.out,第一行为满足要求的活动占用的时间3第二行为最大集合中的活动序号，每个数据之间用一个空格隔开。【样例输入】113514121481206811610573859213【样例输出】142368【题解】我们使用的贪心策略如下。即每一步总是选择这样的活动来占用资源：使得余卜.的未调度时间最大化，是的兼容的活动尽可能多。为了达到这个目的，我们将n个待选活动按结束时间递增的顺序排序：el'<=e2*<=•••<=€!!*o首先将递增序列的活动1进入集合So然后依次分析递增序列中的活动2,活动3,……，活动n,每次将与S中的活动兼容的活动加入到集合S中。我们结合问题的样例输入，先将11个活动的活动号、开始时间、结束时间及递增编号表按照以上这种贪心策略，贪心选择如下：时间0 1 2 3 4 5 6 7 8 9 11121314选择活动 H—H—I—I—H—I—H—I—H2 活动2兼容（持续时间1—4）,加入S,S={2},t=4不兼容，放弃不兼容，放弃8 活动8兼容（持续时间5—7）,加入S,S={2,8},t=7不兼容，放弃不兼容，放弃7 不兼容，放弃6 活动6兼容（持续时间8—11）,加入S,S={2,8,6},t=ll4 不兼容，放弃11不兼容，放弃3 活动3兼容（持续时间12—14）,加入S,S={2,8,6,3},t=14所以问题的解：t=14,S={2,8,6,3）o【标程】#iiiclude<iostieam>#iiiclude<cstdio>#iiiclude<algontlun>usingnamespacestd;stiuctstu（inta;intb;intc;}s[1005];boolcmp（stux,stuy）（returnx.b<y,b;}mtd[1005]={0};hitintnj;scanff%cT.&n);for(i=O;i<n;i++)scanf(”%d%dH,&s[i].a,&s[i].b);s[i],c=i+l;}sort(s,s+n.cmp);intsum=O;intmin=s[O].b;sum=s[O].b-s[O].a+1;for(i=l;i<n;i++)if(niui<s[i].a)(niiii=s[i].b;sum=sum-rs[i].b-s[i].a+1;)}piintf("%d\n”,sum);miii=s[O].b;d[s[O].c]=l;for(i=l;i<n;i++)if(niui<s[i].a)(niiii=s[i].b;d[s[i].c]=l;)}fbr(i=1;i<=1005;i++)if(d[i]!=0)printf("%d”,i);return0;}【例3-4]雇用计划【问题描述】一位管理项目的经理想要确定每个月需要的工人，他当然知道每月所需的最少工人数。当他雇用或解雇一个工人时会有一些额外支出。一旦一个工人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个人的费用，解雇一个人的费用和一个个工人的工资。现在他在考虑一个问题：为了把项目的费用控制在最低，他将每月雇用或解雇多少个工人。输入：输入文件含有三行。第一行为月数n(iv=n<=12)。第二行含雇佣一个工人的费用，一个工人的工资和解雇一工人的费用(<=100).第三行含11个数，分别表示每月最少需要的工人数(<=1000)»每个数据之间用一个空格隔开。输出：输出仅一行，表示项目所需的最小总费用。【样例输入】345610911【样例输出】199【题解】我们从第一个月开始，逐月计算现有工人数，先发给这些人工资。如果雇用新工人，则必须给新上岗工人发放雇用费用；如果削减了部分工人，则必须给下岗工人发放解雇费用。当月发放的工资+雇佣(或解雇)的费用构成了一个月的总费用。我们从第一个月开始，逐月累计项目总费用，直至算出n个月的总费用为止。问题是怎样将这笔费用控制到最低？这mincost表示最小费用和，初始时mincost=0；now表示现有工人数，初始时now=0：表示第1个月所需的最小工人数(l〈=i<=n)；n表示月数：f表示解雇费用：s表示工资；h表示雇用费用。则我们需要解决下面两个问题：.怎样在当月工人数不足情况下确定雇用方案如果第1个月的所需最小人数mm[□大于现有工人数now,则需要雇佣工人。为了尽可能减少雇用费用，我们不妨雇用(nun[i]-now)个工人，使第1个月工人数正好为如果imn[i]=now,则维持现有工人数now不变。.怎样在当月工人数多于的情况下确定解雇方案我们选取这样的贪心策略去确定：尽可能少地解雇工人，并且在工资合理支出的前提下尽可能使现有工人数维持在一个最长时间内，以减少雇佣和解雇的额为支出。【标程】progiainlik;varij,fs,h,n,nun,c,max:longint;a:anay[0..12]oflongint;begmassign(input,'in.txt');reset(input);assign(output,'out.txt');lewnte(output);readlii(n);a[0]：=0;c:=0;readlii(h,s,f);fori:=ltondoread(a[i]);niax:=(h+f)divs+1;fori:=ltondobeginifa[i]>=a[i-l]thenc:=c+a[i]*s+(a[i]-a[i-1])*h;ifa[i]<a[i-l]thenbeginniin:=O;fbrj:=i+ltoi+maxdoif(j<=n)and(a[j]>nun)thenimn:=alj];ifnun<a[i]thenbeginc:=c+#(a[i]-min);a[i]:=a[i]-nun;a[i+l]:=a[i];endelsebegina[i]:=a[i-l];ifa[i+l]<a[i]thena[i+l]：=a[i];end;c:=c+a[i]*s;end;end;wiiteln(c);close(iiiput);close(output);end.【例3・5】旅行家的预算【问题描述】一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市的距离Did,汽车油箱的容量C(以升为单位)，每升汽油能行驶的距离Dic2,出发时每升油的价格为p0沿途有n个油站(l<=nv=100)，油站1离出发点的距离di,该油站每升汽油的价格pi(1=1,2,…，n)。请编程输出完成任务的最小费用，计算结果四舍五入这小数点后两位，如果无法到达目的地，则输出"Nosolution\输入：输入文件名为：。止皿，共n+1行，第一行为：DidCDic2Pn,以下n行，其中第i+1(1<=:<=!!)行的数据均有2个：该油站据出发点的距离di,该油站每升汽油的价格pi。每个数据之间用一个空格隔开。输出：输出文件名为：oil.out,仅一行,表示最小费用。【样例输入】275.611.927.42.82102.02.9220.02.2【样例输出】26.95【题解】设出发的城市为0站，目的城市为n+1站。汽车目前在I站(0<=i<=n),应加多少油，驶往那一站可是整个行程的花费最少？我们不妨采用下面的贪心策略：下一个目的站的单位油价尽可能低于1站，如果所有可达油站的单位油价都高于1站的话，则下一个目的站的油价也应该尽可能的便宜。【标程】第一种解法：#iiiclude<cstdio>usingnamespacestd;doubledl,c,d2.p,a[20000]={0},b[20000]={0},count=0;hitmam()(intnjj,k;doubleniin.pie=0;scanf("％lf%lf%lf%lf%d';&d1,&c,&d2,&p,&n);a[0]=p;b[n+l]=dl;for(i=l;i<=n;i++)scanf(H%lf%lf;&b[i],&a[i]);for(i=0;i<n+l;)a[n+l]=a[i];nwi=1000000.0;if(b[i+l]-b[i]>c*d2)(prmtf('NoSoh】tion\iT);return0;)for(j=i+l;b|j]-b[i]<=c*d2&&j<=n+lJ++)if(a[j]<=niiii){niHi=a[j];k=j;}if(a[k]<=a[i])(if(pre*d2<b[k]-b[i])(count+=a[i]*((b[k]-b[i])/d2-pre);pre=0;)elsepre-=(b[k]-b[i])/d2;)elsecount+=(c-pre)*a[i];pre=c-(b[k]-b[i])/d2;)i=k;}piintf("%.21fn",count);return0;}第二种解法：#iiiclude<cstdio>#iiiclude<cstdlib>usingnamespacestd;#definemaxii102doubled[niaxii];doublec;doubled2;doublep[niaxii];hitn;doublecost;doublerest;hit(doubledl;scanff%lf%lf%lf%lf%d”,&d1,&c,&d2,&p[0].&n);fbr(inti=1;i<=n;i-H-)scanf(M%lf%lf;&d[i],&p[i]);}d[n+l]=dl;P[n+1]=0;d[0]=0;cost=0;rest=0;mtk=0;while(k<=n)mtj=k;mtflag=0;mtniin=0;doubleneed=0;while(d|j+l]-d[k]<=c*d2&&j<=n)J++；if(flag==0&&p[j]<p[k])(flag=J；)==0||p[j]<p[nun])(min=j;))】f(k=J)(printfC'NoSolution^");return0;)if(flag==0)(need=c-rest;cost+=need*p[k];rest=c-(d[inin]-d[k])/d2;k=inin;)else(need=(d[flag]-d[k])/d2-rest;if(need<0)(need=0;)cost+=need*p[k];rest=0;k=flag;)}return0;}【例3・6】线段覆盖【问题描述】给定X轴上的N(0<N<100)条线段。每个线段由他的两个端点ai和bi确定，i=L2,……,No这些坐标都是区间(-999,999)的整数。有些线段会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段之间两两之间没有内部公共点。输入：输入文件名为：cover.mo第一行是一个整数n0接下来又n行，每行有两个空格隔开的整数,表示一条线段的两个端点的坐标。输出：输出文件名为：cover.out,第一行是一个整数表示最多剩下的线段数。接下来有这么多行（按照坐标升序排列剩下的线段），每行两个整数分别表示一条线段的左端点和右端点。如果有多解，只需输出其中一组解即可。【样例输入】631325【样例输出】【题解】我们选取的贪心策略为：每次选取线段右端点坐标最小的线段，保留这条线段，并把和这条线段有共部分的所有线段删除。重爱这个过程，直到任两条线段之间多没有公共部分。【标程】#iiiclude<cstdio>#iiiclude<algonthin>#iiiclude<iostieam>usingnamespacestd;stmctstu{mt1;intr;}a[1001];boolcmp(stux,stuy){returnx.r<y,r;mtintn;intaiis;scanf(H%d';&n);ans=n;for(mti=0;i<n;i++)scaiif(M%d%d,\&a[i].L&a[i].r);if(a[i].l>a[i].i)swap(a[i].l,a[i].r);)sort(a+0,a+n,cmp);mti=0;//i用来记录当前位置的线段intss=l;while(i+ss<n)if(a[i].i〈=a[i+ss].l&&(i+ss<n))〃不相交时(1=1+SS；〃更新状态，跳到与之比较的线段ss=l;)elseif(5].1"口+55]・1&&：1口].1<=讥1+55]・1&&。+55<11))〃部分相交(ans";SS++；)elseif(a[i].r>a[i+ss].l&&a[i].1>a[i+ss]/&&(i+ssvn))〃覆盖，前一条比后一条长(ans";i++；ss=l;)}prin氓"％d”,ans);return0;【例3-7］智力大冲浪【问题描述】小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为n个时段(11W500),它又给出了很多小游戏，每个小游戏都必须在规定期限H前完成(iWHWn)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi,wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱！【输入】输入文件hddle.in,共4行。第1行为m,表示一开始奖励给每位参赛者的钱；第2行为11,表示有n