【文章內(nèi)容簡介】 boolean。 begin num:=0。 readln(m,n)。 while (m0)and(n0) do begin inc(num)。 fillchar(f,sizeof(f),false)。 for i:=1 to n do begin read(a[i])。 f[a[i]]:=true。 end。 readln。 max:=0。 win:=0。 for k:=m*n downto 1 do begin if f[k] then begin inc(win)。 if winmax then max:=win。 end else dec(win)。 end。 writeln(39。Case 39。,num,39。: 39。,max)。 readln(m,n)。 end。 end. ? 例題 10：取數(shù)游戲 ? 給出 2n（ n≤100）個自然數(shù)（數(shù)小于等于 30000）。游戲雙方分別為 A方（計算機方）和 B方（對弈人）。只允許從數(shù)列兩頭取數(shù)。 A先取，然后雙方依次輪流取數(shù)。取完時，誰取得的數(shù)字總和最大為勝方；若雙方和相等，屬于 A勝。試問 A方可否有必勝的策略？ ? 輸入：鍵盤輸入 n及 2*n個自然數(shù) ? 輸出：共 3n+2行，其中前 3*n行為游戲經(jīng)過。每行分別為 A方所取的數(shù)，及 B方取數(shù)前應(yīng)給予的適當提示，讓游戲者選取哪一頭的數(shù)（ L/R 左端或右端），和 B方所取的數(shù)。最后 2行分別為 A方取得的數(shù)之和， B方取得的數(shù)之和。 ? 問題分析： ? 設(shè) n=4，自然數(shù)列為： 7 9 3 6 4 2 5 3 。 ? 設(shè)計一個貪心策略，讓 A每次取數(shù)列兩頭最大的 數(shù)。 ? A?。? 5 ? B?。? 3 ? 有效策略：若能夠讓 A方取走 “ 數(shù)和較大的奇（偶）位置上的所有數(shù) ” ，則 A方勝。 ? 設(shè) j為 A取數(shù)的奇偶位置標志，則 j=0表示偶數(shù)位置數(shù)和較大， A取偶數(shù)位置上的所有數(shù)； j=1表示奇位置數(shù)和交大， A取奇位置的所有數(shù)。 ? 設(shè) SA， SB分別表示 A方取數(shù)和， B方取數(shù)和（ SASB）； a存儲 2*n個自然數(shù)序列；lp， rp為序列左端位置和右端位置； ch為 B方取數(shù)位置信息（ ‘ L?或 ‘ R?）。 ? 讀入 n及 a； ? SA:=0。SB:=0。 {計算 A方取數(shù)和、 B方取數(shù)和， A方取數(shù)的位置標志 } ? for i:=1 to n do ? begin SA:=SA+a[2*i1]。 SB:=SB+a[2*i]。 end。 ? if SA=SB then j:=1 else begin ? j:=0。 交換 SA和 SB； ? end。 ? lp:=1。rp:=2*n。 ? for i:=1 to n do {A方和 B方依次進行 n次對弈 } ? begin ? if((j=1)and(lp mod 2=1))or((j=0)and(lp mod 2=0)){若 A方應(yīng)取奇位置數(shù)且左端位置為奇，或者 A方應(yīng)取偶位置數(shù)且左端位置為偶，則 A方取走左端位置的數(shù) } ? then begin writeln(a[lp])。 lp:=lp+1。 end。 ? else begin writeln(a[rp])。 rp:=rp1； end。 ? write(39。B=L/R39。)。 {提示信息 } ? repeat {B方取數(shù)，輸入 L或 R} ? readln(ch)。 ? if ch=39。L39。 then begin write(a[lp])。 lp:=lp+1。 end。 ? if ch=39。R39。 then begin writeln(a[rp])。 rp:=rp1。 end。 ? until (ch=39。L39。)or(ch=39。R39。)。 ? end。 ? 輸出 A方取數(shù)的和 SA和 B方取數(shù)的和 SB。 ? 例題：混合牛奶（ mixing milk） ? 包裝牛奶是一個如此低利潤的生意，所以盡可能低的控制初級產(chǎn)品（牛奶）的價格變得十分重要。請你來幫助包裝牛奶制造商，以可能的最廉價的方式取得他們所需要的牛奶。 ? 包裝牛奶制造公司從一些農(nóng)民那里購買牛奶，每個農(nóng)民賣給牛奶制造公司的價格不一定相同，而且，一只母牛一天只能生產(chǎn)一定量的牛奶，因此農(nóng)民每一天只能有一定量的牛奶可以賣。 ? 每天，包裝牛奶制造商從每個農(nóng)民那里購買一定量的牛奶（少于或等于農(nóng)民所能提供的最大值）。 ? 給出包裝牛奶制造商每日的牛奶需求，連同每個農(nóng)民提供的牛奶量和每加侖的價格，請計算應(yīng)當如何從農(nóng)民那里購買一定量的牛奶，才能使包裝牛奶制造商所要付出的錢最少。 ? 注意：每天農(nóng)民生產(chǎn)的牛奶的總數(shù)對包裝牛奶制造商來說是足夠的。 ? 輸入：第一行 兩個整數(shù)， N和 M ? 第一個數(shù)值 N（ 0≤N≤2022000）是包裝牛奶制造商一天需要牛奶的數(shù)量。 ? 第二個數(shù)值 M（ 0 ≤ M ≤ 5000）是能夠提供牛奶的農(nóng)民的人數(shù)。 ? 第 2到 M+1行 每行兩個整數(shù)， Pi和 Ai ? Pi（ 0 ≤ Pi ≤ 1000）是農(nóng)民 i牛奶的價格。 ? Ai（ 0 ≤ Ai ≤ 2022000）是農(nóng)民 i一天能賣給包裝牛奶制造商的牛奶數(shù)量。 ? 輸出：一個整數(shù)，表示包裝牛奶制造商拿到所需的牛奶所要付出的最小費用。 ? 輸入樣例： ? 100 5 ? 5 20 ? 9 40 ? 3 10 ? 8 80 ? 6 30 ? 輸出樣例： ? 630 ? 貪心策略：不斷向當前價格最低的農(nóng)民購買牛奶，直到買到足夠的牛奶為止。 ? 具體算法實現(xiàn)：將所有的價格按照從小到大的排序，然后順序購買，即每次向當前價格最低的那個農(nóng)民購買牛奶，如果該農(nóng)民手上的牛奶數(shù)量不足以滿足需求，則繼續(xù)向下一個農(nóng)民購買，以此類推，直到買到足夠多的牛奶，此時得到的即為最優(yōu)解。 ? program mixingmilk。 ? var a:array[1..5100] of integer。 ? b:array[1..5100] of longint。 ? c:array[1..5100] of real。 ? n:longint。 ? m:integer。 ? i,j,l:integer。 ? k,t:longint。 ? begin ? assign(input,39。39。)。 rest(input)。 ? assign(output,39。39。)。 rewrite(out)。 ? readln(n,m)。 ? for i:=1 to m do readln(a[i],b[i])。 ? for i:=1 to m1 do ? for j:=i+1 to m do ? if a[i]a[j] then ? begin ? t:=a[i]。 a[i]:=a[j]。 a[j]:=t。 ? t:=b[i]。 b[i]:=b[j]。 b[j]:=t。 ? end。 ? ? i:=0。 j:=0。 k:=0。 repeat i:=i+1。 if n=b[i] then begin k:=k+a[i]*b[i]。 n:=nb[i]。 end else begin k:=k+a[i]*n。 n:=0。 end。 until n=0。 writeln(k)。 close(input)。 close(output)。 end. ? 例題：部分背包問題 ? 給定一個最大載重量為 M的背包和 N種貨物。已知第 i種貨物的重量為 Wi，其總價值為 Pi，設(shè)定 M， Wi， Pi均為整數(shù)，編程確定一個裝貨方案， ? 使得裝入背包中的貨物總價值最大。 ? 分析：在求解裝貨方案時，設(shè)背包中裝入了第 i種貨物的重量為 Xi（0=Xi=Wi） ,顯然當 Xi=0表示背包中沒有裝入該種貨物，問題就轉(zhuǎn)化成如 ? 下形式：確定一組 X1,X2,...,XN，使得它們在滿足 Xi=W（ i=1,2,...,N）的條件下， Xi*（ Pi/Wi）具有最大值。 ? 這里，設(shè) Ti為第 i種貨物的單位重量的價值，問題的目標函數(shù)是總價值S=Xi*Ti，顯然，在裝入相同重量的貨物時，單位重量價值越大，則背 ? 包所裝的貨物總價值越大。因此容易證明，在裝貨過程中，為保證背包中所裝貨物的總價值最大，應(yīng)盡可能選擇單位重量價值越大的物品優(yōu) ? 先裝入。這樣問題的解決就變得非常簡單。 ? 算法的簡單描述： ? program bag。 ? begin ? 讀入數(shù)據(jù)； ? 計算貨物的單位重量價值 Ti，并將它們按從大到小排序； ? 依次選擇單位重量較大的貨物放入背包，直至不能放入； ? 輸出最大價值總和 S和裝貨方案； ? end. ? 例題：合并果子（ noip 042） ? 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 ? 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯觯械墓咏?jīng)過 n1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 ? 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為 1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。 ? 例如有 3種果子，數(shù)目依次為 1， 2， 9。可以先將 2堆合并，新堆數(shù)目為 3，耗費體力為 3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 12，耗費體力為12。所以多多總共耗費體力 =3+12=15?？梢宰C明 15為最小的體力耗費值。 ? 【 輸入文件 】 ? 輸入文件 ，第一行是一個整數(shù) n(1＝ n=10000)，表示果子的種類數(shù)。第二行包含 n個整數(shù)，用空格分隔，第 i個整數(shù) ai(1＝ ai=20220)是第 i種果子的數(shù)目。 ? 【 輸出文件 】 ? 輸出文件 ，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保證這個值小于 231。 ? 【 樣例輸入 】 ? 3 1 2 9 ? 【 樣例輸出 】 ? 15 ? 【 數(shù)據(jù)規(guī)模 】 對于 30％的數(shù)據(jù)，保證有 n=1000： 對于 50％的數(shù)據(jù)，保證有 n=5000； 對于全部的數(shù)據(jù)，保證有 n=10000。 ? 例題 11：活動選擇 ? 假設(shè)有一個需要使用某一資源的 n個活動組成的集合 s， s={1， … ， n}。該資源一次只能被一個活動所占用，每一個活動有一個開始時間 bi和結(jié)束時間 ei（ bi≤ei ）。若 bi≥ej 或者 bj≥ei ，則活動 i和活動 j兼容。 ? 你的任務(wù)是：選擇有相互兼容的活動組成的做大集合。 ? 輸入：輸入文件名為 ，共 n+1行，其中第一行為 n，第二行到第n+1行表示 n個活動的開始時間和結(jié)束時間（中間用空格隔開），格式為： ? n ? b1 e1 ? …… ? bn e