【例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