貪心算法詳解(C++版)

1、【例 3-1】刪數(shù)問題【問題描述】鍵盤輸入一個高精度的正整數(shù)n（ n<=240右順序?qū)⒔M成一個新的正整數(shù)。編程對給定的位），去掉其中任意s 個數(shù)字后剩下的數(shù)字按原左n 和 s，尋找一種方案，使得剩下的數(shù)字組成的數(shù)最小。輸入：NS輸出：最后剩下的最小數(shù)?！緲永斎搿?785434【樣例輸出】13【題解】由于正整數(shù) n 的有效位數(shù)為240 位，所以很自然地采用字符串類型存儲n。那么如何解決哪s 位被刪呢？是不是最大的s 個數(shù)字呢？為了盡可能的逼近目標，我們選取的貪心策略為：每一步總是選擇一個使剩下數(shù)最小的數(shù)字刪去。即按高位到低位的順序搜索， 若各位數(shù)字遞增，則刪去最后一個數(shù)字；否則刪去第一個

2、遞減區(qū)間的首字符，這樣刪一位便形成了一個新數(shù)字串。然后回到串首，按上述規(guī)則再刪下一個數(shù)字。重復(fù)以上過程s 次為止，剩下的字串便是問題的解了?！緲顺獭?include <iostream>#include <cstdio>#include <cstring>using namespace std;char a100001;int main()intn,i,j,l,k;gets(a);cin>>n;l=strlen(a);for(i=1;i<=n;i+)for(j=0;j<l-1;j+)if(aj>aj+1)for(k=j;k<

3、;l-1;k+)ak=ak+1;break;l-;for(i=0;i<l-1;i+)if(ai!='0')k=i;break;for(j=i;j<=l-1;j+) cout<<aj;cout<<endl;return 0;【例 3-2】取數(shù)游戲【問題描述】給出 2n（ n<=100 ）個自然數(shù) (數(shù)小于等于30000)。游戲雙方分別為A 方（計算機）和B 方（對弈的人） 。只允許從數(shù)列兩頭取數(shù)。A 先取，然后雙方一次輪流取數(shù)。取完時，誰取得的數(shù)字總和最大為取勝方；若雙方和相同，屬于A 勝。試問A 方可否有必勝的策略？輸入： 479364

4、253RRRR鍵盤輸入n 以及 2*n 個自然數(shù)。輸出：352463973619共 3n+2 行，其中前3*n 行為游戲過程。每三行分別為方取數(shù)前應(yīng)給與適當?shù)奶崾?，讓游戲者選取那一頭的數(shù)（別為 A 方取數(shù)之和與B 方取數(shù)之和?！緲顺獭緼 方所取的數(shù)和B 方所取的數(shù)，及BL/R 左端或右端） 。最后兩行分program ho;var n,i,j,sa,sb,lp,rp,t:longint;ch:char;a:array1.200of longint;beginreadln(n);for i:=1 to 2*n doread(ai);sa:=0;sb:=0;for i:=1 to n dobegi

5、nsa:=sa+a2*i-1;sb:=sb+a2*i;end;if sa>=sb then j:=1elsebeginj:=0;t:=sa;sa:=sb;sb:=t;end;lp:=1;rp:=2*n;for i:=1 to n dobeginif (j=1)and(lp mod 2=1)or(j=0)and(lp mod 2=0) thenbeginwriteln(alp);inc(lp);endelsebeginwriteln(arp);dec(rp);end;write('B=L/R?');repeatreadln(ch);if ch='L' the

6、nbeginwriteln(alp);inc(lp);end;if ch='R' thenbeginwriteln(arp);dec(rp);end;until(ch='L')or(ch='R');end;writeln(sa);writeln(sb);end.【例 3-3】活動選擇【問題描述】假設(shè)有一個需要使用某以資源的n 個活動組成的集合S， S=1, ， n 。該資源一次只能被一個活動占用，每一個活動有一個開始時間bi 和結(jié)束時間ei（ bi<=ei ）。若 bi>=ej 或 bj>=ei,則活動 i 和活動 j 兼容。你

7、的任務(wù)是：選擇由相互兼容的活動組成的最大集合。輸入：輸入文件名為：act.in，共 n+1 行，其中第一行為n，第二行到第n+1 行表示 n 各活動的開始時間和結(jié)束時間（中間用用空格隔開），格式為：nb1 e1bn en輸出：輸出文件名為： act.out，第一行為滿足要求的活動占用的時間 t，第二行為最大集合中的活動序號，每個數(shù)據(jù)之間用一個空格隔開?！緲永斎搿?13 51 412 148 120 68 116 105 73 85 92 13【樣例輸出】142368【題解】我們使用的貪心策略如下。即每一步總是選擇這樣的活動來占用資源：使得余下的未調(diào)度時間最大化， 是的兼容的活動盡可能多。為了

8、達到這個目的，我們將 n 個待選活動按結(jié)束時間遞增的順序排序：e1 <=e2 <=<=en。首先將遞增序列的活動1 進入集合S。然后依次分析遞增序列中的活動2，活動 3， ，活動 n，每次將與S 中的活動兼容的活動加入到集合S 中。我們結(jié)合問題的樣例輸入，先將11 個活動的活動號、開始時間、結(jié)束時間及遞增編號表按照以上這種貪心策略，貪心選擇如下：時間012345678911121314選擇活動| | |2活動2 兼容（持續(xù)時間1 4），加入 S， S=2， t=41 不兼容，放棄5 不兼容，放棄8活動8 兼容（持續(xù)時間5 7），加入 S， S=2 ， 8 ， t=79 不兼容

9、，放棄10 不兼容，放棄7 不兼容，放棄6活動6 兼容（持續(xù)時間8 11），加入 S，S= 2，8，6，t=114 不兼容，放棄11 不兼容，放棄3活動3 兼容（持續(xù)時間12 14），加入 S，S= 2，8，6，3，t=14所以問題的解：t=14， S= 2， 8，6， 3?！緲顺獭?include<iostream>#include<cstdio>#include<algorithm>using namespace std;struct stuint a;int b;int c;s1005;bool cmp(stu x,stu y)return x.b&l

10、t;y.b;int d1005=0;int main()int n,i;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d %d",&si.a,&si.b);si.c=i+1;sort(s,s+n,cmp);int sum=0;int min=s0.b;sum=s0.b-s0.a+1;for(i=1;i<n;i+)if(min<si.a)min=si.b;sum=sum+si.b-si.a+1;printf("%dn",sum);min=s0.b;ds0.c=1;f

11、or(i=1;i<n;i+)if(min<si.a)min=si.b;dsi.c=1;for(i=1;i<=1005;i+) if(di!=0) printf("%d ",i);return 0;【例 3-4】雇用計劃【問題描述】一位管理項目的經(jīng)理想要確定每個月需要的工人，他當然知道每月所需的最少工人數(shù)。當他雇用或解雇一個工人時會有一些額外支出。一旦一個工人被雇傭， 即使他不工作， 他也將得到工資。 這位經(jīng)理知道雇傭一個人的費用，解雇一個人的費用和一個個工人的工資?，F(xiàn)在他在考慮一個問題：為了把項目的費用控制在最低，他將每月雇用或解雇多少個工人。輸入：輸入文

12、件含有三行。第一行為月數(shù) n（ 1<=n<=12 ）。第二行含雇傭一個工人的費用，一個工人的工資和解雇一工人的費用（ <=100 ）.第三行含 n 個數(shù)，分別表示每月最少需要的工人數(shù)（<=1000 ）。每個數(shù)據(jù)之間用一個空格隔開。輸出：輸出僅一行，表示項目所需的最小總費用?！緲永斎搿?4 5 610911【樣例輸出】199【題解】我們從第一個月開始，逐月計算現(xiàn)有工人數(shù)，先發(fā)給這些人工資。 如果雇用新工人，則必須給新上崗工人發(fā)放雇用費用；如果削減了部分工人， 則必須給下崗工人發(fā)放解雇費用。當月發(fā)放的工資 +雇傭（或解雇）的費用構(gòu)成了一個月的總費用。我們從第一個月開始，逐

13、月累計項目總費用，直至算出n 個月的總費用為止。問題是怎樣將這筆費用控制到最低？這mincost 表示最小費用和，初始時mincost=0 ； now 表示現(xiàn)有工人數(shù)，初始時now=0 ； mini表示第 i 個月所需的最小工人數(shù)（1<=i<=n ）；n 表示月數(shù)； f 表示解雇費用； s 表示工資； h表示雇用費用。則我們需要解決下面兩個問題：1. 怎樣在當月工人數(shù)不足情況下確定雇用方案如果第 i 個月的所需最小人數(shù)mini 大于現(xiàn)有工人數(shù)now，則需要雇傭工人。為了盡可能減少雇用費用，我們不妨雇用（mini-now ）個工人，使第i 個月工人數(shù)正好為mini ；如果mini=n

14、ow，則維持現(xiàn)有工人數(shù)now不變。2. 怎樣在當月工人數(shù)多于的情況下確定解雇方案我們選取這樣的貪心策略去確定： 盡可能少地解雇工人， 并且在工資合理支出的前提下盡可能使現(xiàn)有工人數(shù)維持在一個最長時間內(nèi)，以減少雇傭和解雇的額為支出?！緲顺獭縫rogram hk;var i,j,f,s,h,n,min,c,max:longint;a:array0.12of longint;beginassign(input,'in.txt');reset(input);assign(output,'out.txt');rewrite(output);readln(n);a0:=0;c

15、:=0;readln(h,s,f);for i:=1 to n doread(ai);max:=(h+f) div s+1;for i:=1 to n dobeginif ai>=ai-1 thenc:=c+ai*s+(ai-ai-1)*h;if ai<ai-1 thenbeginmin:=0;for j:=i+1 to i+max doif (j<=n)and(aj>min) thenmin:=aj;if min<ai thenbeginc:=c+f*(ai-min);ai:=ai-min;ai+1:=ai;endelsebeginai:=ai-1;if ai+

16、1<ai thenai+1:=ai;end;c:=c+ai*s;end;end;writeln(c);close(input);close(output);end.【例 3-5】旅行家的預(yù)算【問題描述】一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是空的）。給定兩個城市的距離 Dic1 ，汽車油箱的容量 C（以升為單位） ，每升汽油能行駛的距離 Dic2 ，出發(fā)時每升油的價格為 p。沿途有 n 個油站（ 1<=n<=100 ）,油站 i 離出發(fā)點的距離di，該油站每升汽油的價格pi（ i=1,2, ， n）。請編程輸出完成任務(wù)的最小費用，計算結(jié)果四舍五

17、入這小數(shù)點后兩位，如果無法到達目的地，則輸出“No solution ”。輸入：輸入文件名為：oil.in ，共 n+1 行，第一行為：Dic1（1<=i<=n ）行的數(shù)據(jù)均有2 個：該油站據(jù)出發(fā)點的距離個數(shù)據(jù)之間用一個空格隔開。輸出：C Dic2 P n，以下 n 行，其中第i+1di，該油站每升汽油的價格pi。每輸出文件名為：oil.out ，僅一行，表示最小費用?！緲永斎搿?75.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2【樣例輸出】26.95【題解】設(shè)出發(fā)的城市為0 站，目的城市為n+1 站。汽車目前在i 站（ 0<=i<=n ），

18、應(yīng)加多少油，駛往那一站可是整個行程的花費最少？我們不妨采用下面的貪心策略：下一個目的站的單位油價盡可能低于i 站，如果所有可達油站的單位油價都高于i 站的話，則下一個目的站的油價也應(yīng)該盡可能的便宜?！緲顺獭康谝环N解法：#include <cstdio>using namespace std;double d1,c,d2,p,a20000=0,b20000=0,count=0;int main ()int n,i,j,k;double min,pre=0;scanf ("%lf %lf %lf %lf %d",&d1,&c,&d2,&

19、;p,&n);a0=p;bn+1=d1;for (i=1;i<=n;i+)scanf ("%lf %lf",&bi,&ai);for (i=0;i<n+1;)an+1=ai; min=1000000.0;if (bi+1-bi>c*d2)printf ("No Solutionn");return 0;for (j=i+1;bj-bi<=c*d2&&j<=n+1;j+)if (aj<=min) min=aj;k=j;if (ak<=ai)if (pre*d2<bk-b

20、i)count+=ai*(bk-bi)/d2-pre);pre=0;else pre-=(bk-bi)/d2;elsecount+=(c-pre)*ai;pre=c-(bk-bi)/d2;i=k;printf ("%.2lfn",count);return 0;第二種解法：#include<cstdio>#include<cstdlib>using namespace std;#define maxn 102double dmaxn;double c;double d2;double pmaxn;int n;double cost;double re

21、st;int main()double d1;scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&p0,&n);for(int i=1;i<=n;i+)scanf("%lf %lf",&di,&pi);dn+1 = d1;pn+1 = 0;d0 = 0;cost = 0;rest = 0;int k = 0;while(k<=n)int j = k;int flag = 0;int min = 0;double need = 0;while(dj+1 - dk

22、<= c * d2 && j<=n)j+;if(flag = 0 && pj<pk)flag = j;if(min = 0 | pj<pmin)min = j;if(k = j)printf("No Solutionn");return 0;if(flag = 0)need = c - rest;cost += need * pk;rest = c - (dmin - dk)/d2;k = min;elseneed = (dflag - dk)/d2 - rest;if(need < 0)need = 0;cos

23、t += need * pk;rest = 0;k = flag;printf("%0.2lfn",cost);return 0;【例 3-6】線段覆蓋【問題描述】給定 x 軸上的 N（ 0<N<100 ）條線段。 每個線段由他的兩個端點 ai 和 bi 確定， i=1 ，2， ，N。這些坐標都是區(qū)間（ -999， 999）的整數(shù)。有些線段會相互交疊或覆蓋。請你編寫一個程序，從給出的線段中去掉盡量少的線段，使得剩下的線段之間兩兩之間沒有內(nèi)部公共點。輸入：輸入文件名為： cover.in 。第一行是一個整數(shù) n。接下來又 n 行，每行有兩個空格隔開的整數(shù)，表示一條

24、線段的兩個端點的坐標。輸出：輸出文件名為： cover.out，第一行是一個整數(shù)表示最多剩下的線段數(shù)。接下來有這么多行 （按照坐標升序排列剩下的線段），每行兩個整數(shù)分別表示一條線段的左端點和右端點。如果有多解，只需輸出其中一組解即可?！緲永斎搿?6 31 32 5【樣例輸出】2【題解】我們選取的貪心策略為： 每次選取線段右端點坐標最小的線段， 保留這條線段， 并把和這條線段有共部分的所有線段刪除。重復(fù)這個過程，直到任兩條線段之間多沒有公共部分?！緲顺獭?include<cstdio>#include<algorithm>#include<iostream>

25、using namespace std;struct stuint l;int r;a1001;bool cmp(stu x,stu y)return x.r<y.r;int main()int n;int ans;scanf("%d",&n);ans=n;for (int i=0;i<n;i+)scanf("%d%d",&ai.l,&ai.r);if (ai.l>ai.r) swap(ai.l,ai.r);sort(a+0,a+n,cmp);int i=0;/i 用來記錄當前位置的線段int ss=1;whil

26、e (i+ss<n)if (ai.r<=ai+ss.l&&(i+ss<n) /不相交時i=i+ss;/ 更新狀態(tài)，跳到與之比較的線段ss=1;else if (ai.r>ai+ss.l&&ai.r<=ai+ss.r&&(i+ss<n)/部分相交ans-;ss+;else if (ai.r>ai+ss.l&&ai.r>ai+ss.r&&(i+ss<n)/覆蓋，前一條比后一條長ans-;i+;ss=1;printf("%d",ans);retur

27、n 0;【例 3-7 】智力大沖浪【問題描述】小偉報名參加中央電視臺的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者m 元。先不要太高興！因為這些錢還不一定都是你的？！接下來主持人宣布了比賽規(guī)則：首先，比賽時間分為n 個時段 (n 500)，它又給出了很多小游戲，每個小游戲都必須在規(guī)定期限ti 前完成 (1ti n)。如果一個游戲沒能在規(guī)定期限前完成，則要從獎勵費m 元中扣去一部分錢wi ， wi 為自然數(shù)，不同的游戲扣去的錢是不一樣的。當然，每個游戲本身都很簡單， 保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者， 小偉很想贏得冠軍，當然更想贏取最多的錢！注意：比賽絕對不會讓參賽者賠錢!【輸入】輸入文件 riddle.in ，共 4 行。第 1 行為 m，表示一開始獎勵給每位參賽者的錢；第 2 行為 n，表示有 n 個小游戲；第 3 行有 n 個數(shù)，分別表示游戲1 到 n 的規(guī)定完成期限；第 4 行有 n