版2014年8月4日到5-貪心與搜索

貪心與搜索向鵬達(dá)貪心與搜索是有相關(guān)性的，所以可能采取兩種類型的題交雜的方式，有不少的題目會(huì)同時(shí)用到這兩種方法貪心算法（摘自百度百科）

對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，而僅是做出在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。如果要用貪心算法得到最優(yōu)解，那么要保證貪心算法所得到的局部最優(yōu)解就是整體的最優(yōu)解noip2012提高組

國(guó)王游戲

國(guó)王游戲

(game.cpp/c/pas)

【問(wèn)題描述】

恰逢

H

國(guó)國(guó)慶,國(guó)王邀請(qǐng)

n

位大臣來(lái)玩一個(gè)有獎(jiǎng)游戲。首先,他讓每個(gè)大臣在左、右手上面分別寫(xiě)下一個(gè)整數(shù),國(guó)王自己也在左、右手上各寫(xiě)一個(gè)整數(shù)。然后,讓這

n

位大臣排成一排,國(guó)王站在隊(duì)伍的最前面。排好隊(duì)后,所有的大臣都會(huì)獲得國(guó)王獎(jiǎng)賞的若干金幣,每位大臣獲得的金幣數(shù)分別是:排在該大臣前面的所有人的左手上的數(shù)的乘積除以他自己右手上的數(shù),然后向下取整得到的結(jié)果。

國(guó)王不希望某一個(gè)大臣獲得特別多的獎(jiǎng)賞,所以他想請(qǐng)你幫他重新安排一下隊(duì)伍的順序,使得獲得獎(jiǎng)賞最多的大臣,所獲獎(jiǎng)賞盡可能的少。注意,國(guó)王的位置始終在隊(duì)伍的最前面。

【輸入】

輸入文件為

game.in。

第一行包含一個(gè)整數(shù)

n,表示大臣的人數(shù)。

第二行包含兩個(gè)整數(shù)

a

和

b,

之間用一個(gè)空格隔開(kāi),

分別表示國(guó)王左手和右手上的整數(shù)。

接下來(lái)

n

行,每行包含兩個(gè)整數(shù)

a

和

b,之間用一個(gè)空格隔開(kāi),分別表示每個(gè)大臣左手和右手上的整數(shù)。

【輸出】

輸出文件名為

game.out。

輸出只有一行,包含一個(gè)整數(shù),表示重新排列后的隊(duì)伍中獲獎(jiǎng)賞最多的大臣所獲得的金幣數(shù)。

【輸入輸出樣例】

game.in

3

1

1

2

3

7

4

4

6game.out

2

【數(shù)據(jù)范圍】

對(duì)于

20%的數(shù)據(jù),有

1≤

n≤

10,0

<

a、b

<

8;

對(duì)于

40%的數(shù)據(jù),有

1≤

n≤20,0

<

a、b

<

8;

對(duì)于

60%的數(shù)據(jù),有

1≤

n≤100;

對(duì)于

60%的數(shù)據(jù),保證答案不超過(guò)

109;

對(duì)于

100%的數(shù)據(jù),有

1

≤

n

≤1,000,0

<

a、b

<

10000?？紤]相鄰的兩個(gè)人A，B設(shè)A左手上的數(shù)字是A.left,右手上的數(shù)字是A.right.B同理。當(dāng)A位于B前面時(shí)答案是：max(C/A.right,C*A.left/B.right)當(dāng)B位于A前面時(shí)答案是max(C/B.right,C*B.left/A.right)我們把max拆開(kāi)來(lái)考慮，即通過(guò)分情況考慮來(lái)去掉max。情況一：A.left*A.right<B.right此時(shí)上一頁(yè)的第一個(gè)max函數(shù)中的較大的一項(xiàng)是C/A.right，第二個(gè)max函數(shù)中較大的一項(xiàng)是C*B.left/A.right.（因?yàn)锳.left*A.right<B.right可以推出A.right<B.left*B.right，再推出C/B.right<C*B.left/A.right）。那么比較的就是C/A.right與C*B.left/A.right.因?yàn)锽.left是大于等于一的整數(shù)，所以后者要大（答案劣一些）。所以應(yīng)該把A放在前面。此時(shí)B.left*B.right比較大。情況二：B.left*B.right<A.right那么比較的就是C*A.left/B.right與C/B.right因?yàn)锳.left是大于等于一的整數(shù)，所以前者要大。所以應(yīng)該把B放在前面。此時(shí)A.left*A.right比較大。情況三：其他情況。那么比較的就是C*A.left/B.right與C*B.left/A.right如果A.left*A.right大一些，那么應(yīng)該把B放在前面。也就是說(shuō)按照l(shuí)eft*right從小到大排序我們發(fā)現(xiàn)情況一和情況二也滿足‘最優(yōu)做法是按照l(shuí)eft*right從小到大排序’的性質(zhì)，所以這樣做就行了。這題難點(diǎn)其實(shí)在于高精度乘法除法。累了吧，讓我們看一看搜索搜索的關(guān)鍵是，要找到合適的方法讓效率提高。如果是裸的搜索是很容易編的，所以說(shuō)其藝術(shù)性就在優(yōu)化上。俗話說(shuō)看起來(lái)越簡(jiǎn)單的東西，精通起來(lái)就越難。搜索分為深度搜索（DFS）與廣度搜索（BFS），深度搜索又可以細(xì)分為記憶化搜索和迭代加深搜索(DFS-ID)等。NOIP2011提高組mayan用一句話來(lái)說(shuō)題意，就是，給定一個(gè)存在重力的矩陣，每次只能向左或右交換方塊，連續(xù)3個(gè)或以上的方塊群會(huì)被消除。求操作次數(shù)為N時(shí)的操作步驟。搜索，進(jìn)行優(yōu)化雖然好像優(yōu)化方法說(shuō)出來(lái)之后很容易理解，但是考場(chǎng)上不是很容易都想到因?yàn)轭}目規(guī)定了游戲步數(shù)，而且并沒(méi)有要你使用最少步數(shù)的方法，所以用DFS會(huì)很方便，用BFS會(huì)超空間。如何處理重力問(wèn)題以及消除問(wèn)題？深搜遞歸的時(shí)候參數(shù)要傳一個(gè)結(jié)構(gòu)體，即當(dāng)前局面狀態(tài)。寫(xiě)一個(gè)函數(shù)Down，傳入一個(gè)局面，返回讓當(dāng)前局面中所有懸空的方塊掉下去的局面再寫(xiě)一個(gè)函數(shù)Clear，傳入一個(gè)局面，返回讓當(dāng)前局面中所有可消去的方塊消去后的局面讓當(dāng)前局面輪流調(diào)用這兩個(gè)函數(shù)，直到局面沒(méi)有改變了為止。優(yōu)化左右的交換是等價(jià)的如果當(dāng)前局面某種顏色的方塊個(gè)數(shù)小于等于二，顯然這個(gè)局面就不可能通往勝利了（我當(dāng)時(shí)居然沒(méi)想到...什么？這個(gè)太容易了？大家都比我聰明TT）方塊的掉落，不能改變方塊的列，所以對(duì)于顏色i，如果某列l(wèi)1上某顏色方塊數(shù)量屬于[1,2]區(qū)間，那么必須通過(guò)交換，來(lái)從其他的某列l(wèi)2得到方塊。取一個(gè)l1，且l2最遠(yuǎn)，設(shè)這個(gè)距離為Di，那么必須要把所有顏色的Di消到0。而一次操作最多減少兩個(gè)顏色的Di，因此最少操作次數(shù)為：max{max{Di}(1<=i<=10),(sum(Di)(1<=i<=10)+1)/2}

NOIP2009提高組靶形數(shù)獨(dú)搜索？搜索。依次枚舉每一個(gè)沒(méi)放置數(shù)的格子里所放置的數(shù)。用hh[i][j]記錄第i行是否已經(jīng)填過(guò)j這個(gè)數(shù)了，對(duì)于每個(gè)列和九宮格的記錄同理。但是這樣可能還會(huì)超時(shí)，怎么辦？從右往左，從下往上搜。這個(gè)方法過(guò)于投機(jī)取巧？我們要領(lǐng)會(huì)出題者的意圖——想讓我們用常規(guī)的方法通過(guò)不了某個(gè)數(shù)據(jù)，而改用更高級(jí)的方法。但是一個(gè)數(shù)據(jù)只能讓特定的搜索順序進(jìn)行的搜索變得特別慢，所以說(shuō)如果我們事先隨機(jī)一個(gè)搜索順序，或許就能不被某個(gè)數(shù)據(jù)卡掉。還是感覺(jué)這種方法不夠正義？對(duì)于每個(gè)局面，找出剩下未填的位置中的可填數(shù)字個(gè)數(shù)最少的位置，先填它。比如說(shuō)A位置有4種合法填法，B位置有3種，C位置有5種，就先填B位置。每次進(jìn)入遞歸函數(shù)都要進(jìn)行一遍這個(gè)過(guò)程，太慢？其實(shí)只是讓時(shí)間增加了一倍左右，但是通過(guò)‘先搜分支少的’的方法可以讓運(yùn)行速度呈指數(shù)地加快估計(jì)出題者是想讓我們用dancing-links解決這個(gè)問(wèn)題這是一種算法，用類似二維雙向鏈表的結(jié)構(gòu)優(yōu)化了對(duì)于[精確覆蓋問(wèn)題]的搜索速度，所以說(shuō)只要把原問(wèn)題轉(zhuǎn)化為這種[精確覆蓋問(wèn)題]再搜索就可以極大加快速度。有興趣的同學(xué)可以百度搜一下這種算法，資料很多NOIP2007普及組紀(jì)念品分組普及組的題目都不會(huì)太難，增加信心用貪心每次考慮還沒(méi)有被選過(guò)的最大的物品，然后找一個(gè)能與之價(jià)格加起來(lái)小于那個(gè)上限的最大的物品，組成一對(duì)。注意題目里說(shuō)了每一組最多兩個(gè)物品。如果找不到與之放在一組的物品，那么就單獨(dú)放一組。由于那個(gè)與之放在一組的物品的最大允許價(jià)值是不降的，維護(hù)一個(gè)指針即可。為什么這樣是正確的？如果當(dāng)前考慮到物品A，B是A能組隊(duì)的最大的物品，C的價(jià)值小于B。本來(lái)是A，B一組的，如果變成A，C一組，對(duì)于剩下的未選的物品集合的變化就是多了B少了C，這肯定是不會(huì)比變化之前更優(yōu)的?？紙?chǎng)上如果只能‘意會(huì)’到這種貪心是正確的，怎么辦？寫(xiě)一個(gè)暴力的程序，再寫(xiě)一個(gè)數(shù)據(jù)生成器，與這種貪心方法的程序進(jìn)行對(duì)拍。USACOBetsy'sTour一個(gè)正方形的鎮(zhèn)區(qū)分為N*N個(gè)小方塊（1<=N<=7）。農(nóng)場(chǎng)位于方格的左上角，集市位于左下角。貝茜穿過(guò)小鎮(zhèn)，從左上角走到左下角，剛好經(jīng)過(guò)每個(gè)方格一次。當(dāng)N=3時(shí)，貝茜的漫游路徑可能如下圖所示：1<=N<=7.搜索我們注意到，在任何時(shí)刻，都必須保證和當(dāng)前所在位置不相鄰的未經(jīng)點(diǎn)至少有兩個(gè)相鄰的未經(jīng)點(diǎn)。通過(guò)這種想法，我們可以采取這樣的優(yōu)化：1.對(duì)當(dāng)前點(diǎn)周圍的點(diǎn)D,如果只有一個(gè)與D相鄰的未經(jīng)點(diǎn),則點(diǎn)D為必經(jīng)點(diǎn)（下一步必須走到的點(diǎn)）2.如果當(dāng)前點(diǎn)周圍有兩個(gè)或兩個(gè)以上的符合上述條件的必經(jīng)點(diǎn)，則無(wú)論走哪個(gè)必經(jīng)點(diǎn)都會(huì)造成一個(gè)死胡同，需要剪枝3.如果當(dāng)前點(diǎn)周圍只有一個(gè)必經(jīng)點(diǎn)，則一定要走到這個(gè)點(diǎn)N=7的時(shí)候還是會(huì)超時(shí)不能形成孤立的區(qū)域。如果行走過(guò)程中把路一分為二，那么肯定有一部分再也走不到了，需要剪枝。如果每次都使用floodfill算法找連通塊，所耗時(shí)間會(huì)太多。我們必須有效率地進(jìn)行剪枝。當(dāng)前點(diǎn)左右都是已經(jīng)點(diǎn)(或者是邊界)，而上下都是未經(jīng)點(diǎn)當(dāng)前點(diǎn)上下都是已經(jīng)點(diǎn)(或者是邊界)，而左右都是未經(jīng)點(diǎn)這樣不管怎么走，必然是會(huì)有孤立的區(qū)域，只要將出現(xiàn)這種情況的狀態(tài)都剪掉即可。HNOI2011賽車游戲簡(jiǎn)要題意給你一個(gè)道路每一段的長(zhǎng)度與斜率s，對(duì)這段路來(lái)說(shuō)，如果你用v的速度開(kāi)，那么每公里的耗油量是max(0,a*v+b*s)，其中a,b是題目給定的常數(shù)?？傆土渴墙o定的，問(wèn)開(kāi)完這段道路最短時(shí)間。這題我當(dāng)年得了多少分呢？貪心不妨設(shè)我們把路分成一公里一公里的小段。我們發(fā)現(xiàn)，對(duì)于一小段路，在其上提速1km/h的代價(jià)總是a既然總油量是確定的，綜合上一條信息，這告訴我們，所有小段的速度的和是有限的假設(shè)路分為兩個(gè)小段（每個(gè)小段1km，共2km），在這兩個(gè)小段上的速度分別為x和y，那么我們要所用時(shí)間最少，也就是要1/x+1/y最小，并滿足x+y=C（C是一個(gè)定值）當(dāng)1/x+1/y最小時(shí)顯然有x=y.所以說(shuō)，最優(yōu)的情況一定是所有路段的速度v都是相同的！（允許有一些下坡路段速度大于v，但是這些路段油耗都是零）具體做法？先不考慮下坡路段，算出此時(shí)在其他路段上的速度v如果v大于[最平緩的下坡路段零油耗時(shí)的速度]，說(shuō)明這段下坡的速度不會(huì)比最終其他路段速度快，將其并入‘其他路段’的集合中，再次計(jì)算v。再比較v與[次平緩的下坡路段零油耗時(shí)的速度]，如果v是較大的，就并入，再次計(jì)算v...直到v是較小的為止。NOI2012騎行川藏

Input31000010000105200001585000056Output12531.34496464簡(jiǎn)要題意：一個(gè)道路有N段路，對(duì)于一段長(zhǎng)度是s,風(fēng)阻系數(shù)是k,風(fēng)速是v的路，如果使用V的速度騎行，需要的能量是k*s*(V-v)^2.給定總能量，問(wèn)騎完這個(gè)道路的最短時(shí)間。這道題與上道題有較大的相似性對(duì)于這道題而言，讓一個(gè)小段（1km）的速度加快1km/h，需要的能量是與當(dāng)前速度以及這段的性質(zhì)有關(guān)的。我們需要將上題的方法推廣到更普適的情況，以適應(yīng)這道題設(shè)當(dāng)前有一個(gè)方案，第i段路的速度是V[i]，且讓走這段路所需的時(shí)間減小Δt所需要多耗的能量為de[i]*Δt。其實(shí)de[i]就是這段的耗能E對(duì)于耗時(shí)t的導(dǎo)數(shù)，將t=k[i]/V[i]代入E=k[i]*s[i]*(V[i]-v[i])^2再對(duì)t求導(dǎo)即得de[i]。最優(yōu)方案中，de[1],....,de[N]的值都是相等的。這讓我們先想到，二分最優(yōu)方案的de的值，然后計(jì)算出此時(shí)每一段的速度（計(jì)算速度時(shí)需要解一個(gè)三次方程，可用三分法求解），然后求出總耗能，比較總耗能與給定的耗能，來(lái)決定二分的區(qū)間往哪邊縮小。這種貪心的方法比較巧妙，關(guān)鍵是找出最優(yōu)策略中的不變量——de的值。USACOlatinUSACO上的搜索題好多啊...搜索優(yōu)化有哪些呢1.在第一行的排列已經(jīng)確定以后，第一列的每一種排列對(duì)應(yīng)的方案數(shù)都相同。所以只需要搜索(2,2)到(N,N)的邊長(zhǎng)為n-1的正方形即可（最后乘上第一列的可能方案數(shù)）。且對(duì)于(2,2)這個(gè)位置，填3，4……的方案數(shù)完全一樣（與填1的可能不同），因此只要枚舉填1或者3。2.最后一行不用搜，因?yàn)橐呀?jīng)由之前的確定了（所以只要搜(2,2)-(n-1,n)的矩形）娛樂(lè)題有N個(gè)人，每個(gè)人有一個(gè)黑歷史，一開(kāi)始每個(gè)人只知道自己的黑歷史。然后大家想來(lái)共享黑歷史，目標(biāo)就是讓每個(gè)人都知道所有人的黑歷史。傳遞信息的方式只能是兩個(gè)人進(jìn)行交流，這兩個(gè)人可以把所有的自己已知的黑歷史告訴對(duì)方。信息量再大也沒(méi)事，都算是一次交流。問(wèn)讓每個(gè)人都知道所有人的黑歷史，最少需要多少次交流比如說(shuō)N=3的情況，A，B，C三個(gè)人。A先跟B交流，此時(shí)A知道A和B的黑歷史，B知道AB的，C知道C的。B跟C交流，此時(shí)A知道AB的，B知道ABC的，C知道ABC的。B再跟A交流，此時(shí)大家都知道ABC其中每個(gè)人的了。需要3次。答案是2N-3第一個(gè)人先跟第2...N個(gè)人交流，其中跟第N個(gè)人交流之后，第一個(gè)人和第N個(gè)人都知道了所有人的信息。然后第一個(gè)人只需要跟第2...N-1個(gè)人交流，那么就讓他們都知道了所有人的信息。真是這樣嗎~~~想一想N=4的情況，能不能比5次更少一點(diǎn)呢？比如說(shuō)，4次？4次是可以做到的。A先跟B交流，此時(shí)A和B都知道了AB的信息。C跟D交流，此時(shí)C和D都知道了CD的信息。A跟C交流，此時(shí)A和C都知道了ABCD的信息。B跟D交流，此時(shí)所有人都知道了ABCD的信息。所以，2<=N<=3時(shí)答案是2N-3，N>3時(shí)答案是2N-4N>4時(shí)，方法是讓第4個(gè)人跟5...N交流一遍來(lái)收集信息，然后再按照N=4的情況讓1、2、3、4互換信息，然后第4個(gè)人再跟5...N交流一遍來(lái)下發(fā)信息。如上是2014年8月4日上午的講課內(nèi)容。此題作為中午的思考題被出出來(lái)。USACOmilk4超市中有P個(gè)桶(1<=P<=100)，每個(gè)桶有各自的容積你需要買回最少的桶，使得它們可以量出容積為Q的牛奶(1<=Q<=20000)。你每次可以使用一個(gè)桶，從巨大的牛奶池里裝出等于這個(gè)桶容積的牛奶，放到一個(gè)大罐子里，你需要讓這個(gè)罐子里的牛奶量為Q。你不能進(jìn)行其他類型的操作。保證有解搜索因?yàn)轭}目中要求桶數(shù)最少，而深搜是不知道搜索的層數(shù)的，所以要用到迭代加深搜索。在主函數(shù)中，for循環(huán)從1開(kāi)始枚舉搜索層數(shù)（也就是使用的桶數(shù)），在for循環(huán)里面調(diào)用搜索函數(shù)（其中有一個(gè)參數(shù)是我們當(dāng)前定下的搜索層數(shù)）。如果找到解，就跳出循環(huán)?？梢杂脧V搜做嗎？應(yīng)該可以，但太耗空間。你可能認(rèn)為迭代加深搜索在定下深度為m+1層的搜索的時(shí)候，重復(fù)了深度為m的搜索已經(jīng)做過(guò)的部分，但由于當(dāng)深度上升時(shí)，搜索所用的時(shí)間呈指數(shù)上升，所以說(shuō)重復(fù)的部分耗時(shí)可以忽略不計(jì)。（這段是應(yīng)一些同學(xué)的要求寫(xiě)的，因?yàn)榉从尘唧w的遞歸過(guò)程不太會(huì)寫(xiě)。不過(guò)應(yīng)該很多人都會(huì)吧..是比較基礎(chǔ)的遞歸）在遞歸函數(shù)里要傳入一個(gè)參數(shù)k，代表我們已經(jīng)考慮完前k個(gè)桶了，那么當(dāng)前只需考慮將第k+1~第P個(gè)桶中的哪個(gè)桶放入買桶的集合，然后再遞歸下去（傳下去的參數(shù)為當(dāng)前選擇的桶的編號(hào)）。當(dāng)搜索到一個(gè)組合，判斷用這些牛奶桶是否可以得到解的時(shí)候，要結(jié)合動(dòng)態(tài)規(guī)劃的方法來(lái)做。設(shè)f[i]為用這些桶是否能夠量出容量為i的牛奶，它是一個(gè)布爾型數(shù)組。初始條件為f[0]=1，其他f的值都為0.狀態(tài)轉(zhuǎn)移方程f[i]=f[i]orf[i-v[j]](j為使用的所有牛奶桶)目標(biāo)狀態(tài)為f[Q]如果f[Q]為1，則當(dāng)前解合法，直接輸出即可。

我們可以邊搜索，邊進(jìn)行f數(shù)組的修改（要記錄哪些位置被修改了，方便回溯）如果當(dāng)前桶的容積是V，但是f[V]=1，說(shuō)明通過(guò)之前的桶的組合就可以代替當(dāng)前桶了，剪掉這種情況。由于直觀上會(huì)覺(jué)得小的桶更加有用，所以事先將桶按照容積從小到大排序，再進(jìn)行搜索，效果會(huì)更好。我們發(fā)現(xiàn)，對(duì)于一個(gè)桶的集合，如果是最優(yōu)方法的話，肯定每一個(gè)桶都要用到。否則方法可以更優(yōu)。也就是說(shuō)，如果大小為x的容量可以不使用當(dāng)前剛加入的桶就能達(dá)到了，我們不妨認(rèn)為這種容量是‘達(dá)不到的’。也就是f[x]賦為0.具體來(lái)說(shuō)，我們?cè)诿看渭油皝?lái)更新f數(shù)組之前，把f數(shù)組復(fù)制一遍，設(shè)為g。更新之后，如果有某個(gè)i滿足g[i]=1，那么就令f[i]=0，因?yàn)檫@個(gè)容量之前就已經(jīng)是可以達(dá)到的了。讓f中1的個(gè)數(shù)盡量少，為什么能夠優(yōu)化呢？注意到，我們的轉(zhuǎn)移方程也可以看為，對(duì)于每個(gè)i

,若f[i]=1，則令f[i+v[j]]=1.（v[j]是剛剛加入的桶的容量）因?yàn)閒[i]=1的i的個(gè)數(shù)比較少，我們可以用一個(gè)數(shù)組去記錄哪些位置上的f[i]=1，于是我們更新一次f所需復(fù)雜度只是f中1的個(gè)數(shù)了。帶權(quán)中位數(shù)問(wèn)題SGU114給你N個(gè)東西，每個(gè)東西有兩個(gè)性質(zhì)a[i]（數(shù)值）和b[i]（權(quán)重）你要找到一個(gè)數(shù)X，使得sigma{abs(a[i]-x)*b[i]}最小。如果每個(gè)b[i]都是1，那么問(wèn)題就等價(jià)于找中位數(shù)。貪心先將東西按照a從小到大排序。求出b[i]的和，設(shè)為B。先令temp=0。從前往后掃描東西，讓temp+=b[i].當(dāng)temp首次大于B/2時(shí)，當(dāng)前的東西的a值就是x的最優(yōu)值（之一）。最優(yōu)性顯然吧考慮將x變小或者變大，答案都不會(huì)更優(yōu)。為便于理解，可以考慮每個(gè)東西的b值都為1的情況，那么就是樸素的中位數(shù)的問(wèn)題，上一頁(yè)所說(shuō)的用temp進(jìn)行的那個(gè)過(guò)程顯然是對(duì)的。然后我們可以把第i個(gè)東西拆成b[i]個(gè)b值為1的東西。（如果b[i]是1.5，你就拆成1.5個(gè)b值為1的東西...雖然你會(huì)覺(jué)得很詭異，但的確可以這么理解）SGU313題目大意：在一個(gè)長(zhǎng)為L(zhǎng)（10^9）的環(huán)形跑道上，有n(n<=50000)個(gè)X，n個(gè)O，他們每個(gè)都位于跑道的某個(gè)整數(shù)位置上——我們以某個(gè)點(diǎn)為起點(diǎn)，位置即為順時(shí)針離起點(diǎn)的距離。告訴你每個(gè)X和O的坐標(biāo)，請(qǐng)你找出一種配對(duì)方案，使得每個(gè)X跑到自己心愛(ài)的O那里所經(jīng)過(guò)的長(zhǎng)度之和最短。輸出每個(gè)X配對(duì)的是第幾個(gè)O。如果不是一個(gè)環(huán)而是一個(gè)直線就很好做了，直接O（n）模擬掃一遍，開(kāi)一個(gè)棧存放還未匹配的點(diǎn)編號(hào)，注意這些點(diǎn)可能是X集合的也可能是O，因?yàn)樗麄兊南群鬀](méi)有規(guī)定。問(wèn)題就是要找一個(gè)分割點(diǎn)，從這個(gè)分割點(diǎn)分割開(kāi)后再對(duì)形成的一條直線進(jìn)行上述操作。首先我們證明對(duì)最優(yōu)方案，必定存在至少一根X、O中間的子線段，他們中間是沒(méi)被任何匹配線覆蓋的（即能找到一個(gè)分割點(diǎn)）。對(duì)上面這個(gè)圖，他必定不是最優(yōu)方案。為什么呢？我們可以對(duì)所有交叉的匹配進(jìn)行調(diào)整，使得調(diào)整后肯定不比原來(lái)差，且有分割點(diǎn)存在。對(duì)于原來(lái)的X和O的順序是X、X、O、O的一個(gè)子集，其中第1個(gè)和第3個(gè)連，2和4連，我們把它調(diào)整成1和4連，2和3連，這樣答案不變。假設(shè)最優(yōu)方案沒(méi)有分割點(diǎn)，那么調(diào)整之后答案不變，但是必有一條最長(zhǎng)的匹配已經(jīng)包圍了整個(gè)環(huán)了，這顯然是荒謬的。下一步就是枚舉分割點(diǎn)（其實(shí)是分割線段）。但是枚舉是O(N)的，加上判斷o（n），明顯超時(shí)。我們要探尋神奇的性質(zhì)。我們先隨便假設(shè)一個(gè)點(diǎn)為起點(diǎn)（不妨設(shè)排序后第一個(gè)點(diǎn)）。若以此點(diǎn)所在線段進(jìn)行分割，那么求得答案就是每條線段長(zhǎng)度*架在它上面的匹配邊的條數(shù)的和。架在它上面的匹配邊的條數(shù)，這個(gè)有神奇的性質(zhì)。掃一遍的過(guò)程中，每碰到一個(gè)黑點(diǎn)，下一截的線段標(biāo)記+1，碰到白點(diǎn)就-1。我們發(fā)現(xiàn)架在它上面的匹配邊的條數(shù)即為線段標(biāo)記的絕對(duì)值.比如XXOOOX，架在相應(yīng)線段上面的匹配邊的條數(shù)即為1210|-1|0.（也就是121010）

那么，當(dāng)匹配點(diǎn)往后移一位時(shí)，相當(dāng)于是最左邊的點(diǎn)移到了最右邊，若最左邊是X，那么線段變成了XOOOXX，新標(biāo)記就是010|-1||-2||-1|我們驚奇的發(fā)現(xiàn)，所有邊的標(biāo)記都-1了！

假設(shè)我們枚舉的分割點(diǎn)為k。k點(diǎn)的前綴和是vk(黑點(diǎn)為1，白點(diǎn)-1)。那么所有邊新標(biāo)記變成了原標(biāo)記-vk!

那么，相當(dāng)于找一個(gè)數(shù)，讓它與所有線段原標(biāo)記的差絕對(duì)值*對(duì)應(yīng)線段長(zhǎng)度的值盡量小。

我們發(fā)現(xiàn)，這就是一個(gè)帶權(quán)中位數(shù)模型（sgu114是裸的帶權(quán)中位數(shù)模型）折半搜索（雙向廣搜）比如這樣一道題九宮格的華容道游戲大家都知道吧，每個(gè)格子有一個(gè)1~8的數(shù)，還有一個(gè)格子是空的給你初始狀態(tài)和結(jié)束狀態(tài)，問(wèn)你有沒(méi)有N步以內(nèi)從初始狀態(tài)變換到結(jié)束狀態(tài)的方法，如果有的話輸出步驟N很大怎么辦呢？我們可以搜索（深搜廣搜均可）出從初始狀態(tài)開(kāi)始走N/2步（向上取整）可以到達(dá)的狀態(tài)，把這些狀態(tài)用一個(gè)數(shù)字（就像MD5碼一樣?。┍硎?，存在哈希表里（通過(guò)掛鏈的方式，也就是哈希表只是一個(gè)索引，在掛著的鏈上存儲(chǔ)具體的九宮格狀態(tài)。這樣是為了避免兩個(gè)實(shí)際上不同的狀態(tài)卻算出了同樣一個(gè)數(shù)字）注意，搜索的時(shí)候要判重然后我們?cè)購(gòu)慕Y(jié)束狀態(tài)開(kāi)始，搜索N/2（向下取整）步，然后對(duì)于每一種狀態(tài)，也用一個(gè)數(shù)字表示，并且在哈希表內(nèi)查找這種狀態(tài)是不是被記錄過(guò)。如果被記錄過(guò)，就說(shuō)明從兩邊的搜索到達(dá)了同樣的一個(gè)狀態(tài)，說(shuō)明這是一個(gè)解。就像挖隧道一樣如果你確定了隧道的開(kāi)始點(diǎn)和結(jié)束點(diǎn)，選擇只從一邊挖的話，如果要恰好挖到結(jié)束點(diǎn)，需要嘗試很多次但如果先從開(kāi)始點(diǎn)開(kāi)始挖一半的路程并且在挖到的地方做上標(biāo)記（嘗試許多次，做上許多標(biāo)記），再?gòu)慕Y(jié)束點(diǎn)開(kāi)始挖一半的路程，只要找這種標(biāo)記就行，就可以減少嘗試次數(shù)折半搜索的搜索過(guò)程就像一個(gè)菱形如上是2014年8月4日的講課內(nèi)容。tyvj的一道題在烈日下工作了一個(gè)月的你，七夕了，你要給妹子送禮物，禮物當(dāng)然是一塊純手工的磚，每次妹子看到這塊磚就能想起你。這里有N個(gè)泥土塊（N<=45），每個(gè)塊有一定的質(zhì)量，你可以選擇其中一些泥土塊去燒結(jié)成你的磚，而你對(duì)燒成的磚的質(zhì)量有要求，它必須是一個(gè)精確的值，Q克(1<=Q<=10^8)，也就是你要找出一些塊，他們的質(zhì)量和恰好是Q。問(wèn)是否有可行方案?？吹絅的大小，很誘人吧，很奇怪吧，45？45除以2大約等于22，而使用O(2^N)的爆搜所能承受的最大N值大約也是這么多。于是想到了折半搜索先搜索前22個(gè)土塊能組成的質(zhì)量，存在哈希表里，再搜索后22個(gè)土塊能組成的質(zhì)量，比如當(dāng)前在后22個(gè)土塊中搜到的質(zhì)量和是x，然后在哈希表里查找是否存在Q-x這個(gè)值（也就是前22個(gè)土塊中是否存在和為Q-x的組合）。USACOprime3在下面的方格中，每行，每列，以及兩條對(duì)角線上的數(shù)字可以看作是五位的素?cái)?shù)。方格中的行按照從左到右的順序組成一個(gè)素?cái)?shù)，而列按照從上到下的順序。兩條對(duì)角線也是按照從左到右的順序來(lái)組成。這些素?cái)?shù)各個(gè)數(shù)位上的和必須相等。左上角的數(shù)字是預(yù)先定好的。一個(gè)素?cái)?shù)可能在方陣中重復(fù)多次。如果不只有一個(gè)解，將它們?nèi)枯敵觯ò凑者@25個(gè)數(shù)字組成的25位數(shù)的大小排序）。一個(gè)五位的素?cái)?shù)開(kāi)頭不能為0（例如：00003不是五位素?cái)?shù)）輸入：一行包括兩個(gè)被空格分開(kāi)的整數(shù):各數(shù)位上的數(shù)字的和以及左上角的數(shù)字。輸出：對(duì)于每一個(gè)找到的方案輸出5行，每行5個(gè)字符,每行可以轉(zhuǎn)化為一個(gè)5位的質(zhì)數(shù).在兩組方案中間輸出一個(gè)空行.如果沒(méi)有解就單獨(dú)輸出一行"NONE"。搜索優(yōu)化？一行行的順序枚舉連樣例都過(guò)不了(....)先枚舉兩條對(duì)角線，因?yàn)樗麄兛刂频男辛惺亲疃嗟模易笊辖堑臄?shù)已經(jīng)確定了。再枚舉中間的一豎列,因?yàn)樗瑯涌刂频男辛凶疃?再枚舉最上面一行和最下面一行。此時(shí)第3行的2，4兩個(gè)數(shù)也可以通過(guò)減法得到了。最后枚舉第2，4行，第3行可以通過(guò)減法得到。于是所有格子都已經(jīng)確定了，驗(yàn)證一下就行。由于要適應(yīng)這種奇葩的搜索順序，需要多個(gè)數(shù)組記錄滿足條件的素?cái)?shù)，比如已知第1,3,5位的所有素?cái)?shù)，或已知第1位的所有素?cái)?shù)都要預(yù)處理出來(lái)。并且每個(gè)數(shù)用5個(gè)1位數(shù)儲(chǔ)存（也就是用一個(gè)大小為5的數(shù)組儲(chǔ)存...），這樣操作方便而且效率高。你問(wèn)我怎么想出來(lái)這種奇葩的搜索順序的？呵呵，我也不知道，看題解才想出來(lái)的（如果是考場(chǎng)上想出來(lái)真的要靠功力和造化）不過(guò)如果知道了這種方法之后，理解起來(lái)還是不難的如果不知道哪種搜索方式比較快，可以編個(gè)數(shù)據(jù)生成器，自己試試一種方便的調(diào)試方法有某位弱得跟粉一樣的渣詢問(wèn)我調(diào)試程序的一些技巧，所以我準(zhǔn)備作為飯后甜點(diǎn)講一講~比如你有一個(gè)遞歸函數(shù)intwork(intp){...

}然后你發(fā)現(xiàn)好像有的時(shí)候p會(huì)變成負(fù)值，但是p是負(fù)值就是出現(xiàn)bug的時(shí)候，你想跳轉(zhuǎn)到這種時(shí)候。那么你可以這么寫(xiě)intxxx（隨便多定義一個(gè)全局變量）intwork(intp){if(p<0)xxx=0;...

}然后把斷點(diǎn)設(shè)在xxx=0那一行處，再點(diǎn)調(diào)試，就可以在運(yùn)行到那一行時(shí)停下，此時(shí)正好p是小于零的。為什么要寫(xiě)xxx=0呢？你寫(xiě)其他的也是一樣的，比如用p=p代替xxx=0，總之目的就是讓那里有一個(gè)語(yǔ)句，有一個(gè)東西..不過(guò)有的時(shí)候編譯器會(huì)自動(dòng)把p=p或者p=p+1-1這種語(yǔ)句過(guò)濾掉，因?yàn)樗鼤?huì)認(rèn)為這是碼農(nóng)們偶爾精神出問(wèn)題時(shí)寫(xiě)下的廢話HNOI2010matrix矩陣A和矩陣S都是N*M的非負(fù)整數(shù)矩陣。矩陣A的元素都小于P矩陣S的第一行和第一列均為0;且滿足S[i,j]=A[i,j]+A[i-1,j]+A[i,j-1]+A[i-1,j-1]（i,j>1）給出N,M,P，以及矩陣S求字典序最小的矩陣A使得滿足條件。30%：N,M≤10另30%：P=2100%：1＜N,M≤2001＜P≤10如果A的第一行與第一列已經(jīng)確定，那么我們就可以按部就班地算出A的所有元素的值了。這樣一來(lái)需要決策的元素個(gè)數(shù)就從200的平方變成了399。我們?cè)噲D建立A[i,j]與第一行或第一列之間的直接等式關(guān)系。以下是一個(gè)較易理解的建立等量關(guān)系的方法：首先不看元素在0到P-1范圍內(nèi)的限制，設(shè)A1,k和Ak,1都為0，并計(jì)算將A補(bǔ)全。（此時(shí)A中可能有負(fù)數(shù)或者大于等于P的整數(shù)）我們只需要搜索A的第一行，每當(dāng)確定一個(gè)元素，就可以更新A[j,1]的取值范圍。根據(jù)公式，除了A[1,1]以外，A[i,1]的取值是互不影響的。不斷更新第一列每個(gè)元素的可以取值的范圍，一旦出現(xiàn)有某個(gè)元素下界大于上界的情況就剪枝。顯然這樣搜索的字典序是最優(yōu)的。USACOcryptcow農(nóng)民Brown和John的牛們計(jì)劃協(xié)同逃出它們各自的農(nóng)場(chǎng)。它們?cè)O(shè)計(jì)了一種加密方法用來(lái)保護(hù)它們的通訊不被他人知道。如果一頭牛有信息要加密，比如"InternationalOlympiadinInformatics"，它會(huì)隨機(jī)地把C，O，W三個(gè)字母插到到信息中（其中C在O前面，O在W前面），然后它把C與O之間的文字和O與W之間的文字的位置換過(guò)來(lái)。這里是兩個(gè)例子：為了使解密更復(fù)雜，牛們會(huì)在一條消息里多次采用這個(gè)加密方法（把上次加密的結(jié)果再進(jìn)行加密）。一天夜里，John的牛們收到了一條經(jīng)過(guò)多次加密的信息。請(qǐng)你寫(xiě)一個(gè)程序判斷它是不是這條信息經(jīng)過(guò)加密（或沒(méi)有加密）而得到的：搜索按從小到大的順序依次找出C,O,W，然后交換中間的兩個(gè)串并將這三個(gè)字符刪掉。如此往復(fù)直到?jīng)]有成對(duì)的C,O,W，判斷一下最后生成的字符串是否是題目所給的串。由于添加的COW是一起的，因此給出的字符串的字符個(gè)數(shù)應(yīng)該等于47（目標(biāo)字符串的長(zhǎng)度）+3*k。如果不滿足就可直接判斷無(wú)解。除了COW三個(gè)字符外，其他的字符的個(gè)數(shù)應(yīng)該和目標(biāo)串相一致。如果不一致也可直接判斷無(wú)解。一個(gè)有解的字符串中，COW三個(gè)字母最早出現(xiàn)的應(yīng)該是C，最后出現(xiàn)的應(yīng)該是W，如果不滿足則剪枝。搜索中間肯定會(huì)出現(xiàn)很多相同的情況，因此需要開(kāi)一個(gè)hash來(lái)記錄搜索到過(guò)哪些字符串，每搜索到一個(gè)字符串，就判重。對(duì)搜索到的字符串，設(shè)不包含COW的最長(zhǎng)前綴為n前綴（同樣也可以定義n后綴），那么如果n前綴不等于目標(biāo)串的長(zhǎng)度相同的前綴，那么當(dāng)前字符串一定無(wú)解，剪枝。N后綴也可采取相同的判斷方法。需要優(yōu)化搜索順序。經(jīng)過(guò)試驗(yàn)我們可以發(fā)現(xiàn)，O的位置對(duì)于整個(gè)COW至關(guān)重要?？梢哉f(shuō)，O的位置決定了整個(gè)串是否會(huì)有解。因此，我們?cè)谒阉鲿r(shí)，應(yīng)該先枚舉O的位置，然后再枚舉C和W的位置。W要倒序枚舉。在判斷當(dāng)前串的子串是否包含在目標(biāo)串中的時(shí)候，可以先做一個(gè)預(yù)處理：記錄每一個(gè)字母曾經(jīng)出現(xiàn)過(guò)的位置，然后可以直接枚舉子串的第一個(gè)字母的位置。這樣比用pos要快2倍左右。APIO2011方格染色（這個(gè)題目不要求做）USACOfence8農(nóng)民John準(zhǔn)備建一個(gè)柵欄來(lái)圍住他的牧場(chǎng)。他已經(jīng)確定了柵欄的形狀，但是他在木料方面有些問(wèn)題。當(dāng)?shù)氐碾s貨儲(chǔ)存商扔給John一些木板，而John必須從這些木板中找出盡可能多所需的木料。當(dāng)然，John可以切木板。因此，一個(gè)9英尺的木板可以切成一個(gè)5英尺和一個(gè)4英尺的木料(當(dāng)然也能切成3個(gè)3英尺的，等等)。John有一把夢(mèng)幻之鋸，因此他在切木料時(shí)，不會(huì)有木料的損失。所需要的木料規(guī)格都已經(jīng)給定。你不必切出更多木料，那沒(méi)有用。（一看就覺(jué)得是美式翻譯）在如下的說(shuō)明中，rail代表的是‘目標(biāo)塊’，board代表的是‘原材料’。采用dfs-id（其實(shí)就是從小到大試驗(yàn)?zāi)芮谐傻膲K數(shù)）來(lái)搜索每一個(gè)rail來(lái)源的board。以下技巧都是針對(duì)這種搜索順序來(lái)制定的。很容易就能注意到，由于每塊rail的價(jià)值是相等的——也就是說(shuō)切小的要比切大的來(lái)的劃算。那么我們?cè)谒阉髂芊袂谐鰅個(gè)rail的方案是自然要選最小的i個(gè)rail來(lái)切。經(jīng)過(guò)一些實(shí)驗(yàn)可以發(fā)現(xiàn)，先切大的rail比先切小的rail更容易提前出解。先切大的board要比先切小的更快。由于r最大可能是1023，但是rail長(zhǎng)度的范圍卻只有0~128，提醒了我們有很多rail的長(zhǎng)度會(huì)是相同的。為減少冗余，若有rail[i+1]=rail[i]，則rail[i+1]對(duì)應(yīng)的board一定大于等于rail[i]對(duì)應(yīng)的board。如果board[i]=board[i+1]，那么從board[i]切下的最大的rail一定大于等于從board[i+1]切下的最大的rail。對(duì)于切剩下的board（無(wú)法再切下rail），統(tǒng)計(jì)一下總和。如果大于board長(zhǎng)度總和-rail長(zhǎng)度總和，一定無(wú)解。HNOI2011任務(wù)調(diào)度搜索+貪心+隨機(jī)調(diào)整對(duì)于每個(gè)隨便順序的點(diǎn)，暴力搜索他屬于類型1還是類型2。注意N<=20，這種指數(shù)復(fù)雜度是可以接受的。并且我們注意到，機(jī)器a一定是先處理完所有類型1的任務(wù)再處理完所有類型2的任務(wù)。機(jī)器b一定是先處理完所有類型2的任務(wù)再處理完所有類型1的任務(wù)。而且如果有兩個(gè)第1類任務(wù)P,Q,在a機(jī)器上P先完成，那么在b機(jī)器上也是讓P先完成。否則一定能夠通過(guò)調(diào)整變成這種情況，且答案不變。貪心的部分然后我們對(duì)于先要在a機(jī)器上運(yùn)行的任務(wù)，以需要在b機(jī)器上運(yùn)行的時(shí)間(從小到大)作為第一關(guān)鍵字，需要在a機(jī)器上運(yùn)行的時(shí)間作為第二關(guān)鍵字，進(jìn)行排序。將排序結(jié)果作為a機(jī)器處理的先后順序。對(duì)于先要在b機(jī)器上運(yùn)行的任務(wù)，以需要在a機(jī)器上運(yùn)行時(shí)間作為第一關(guān)鍵字，在b機(jī)器上運(yùn)行時(shí)間作為第二關(guān)鍵字排序。這只是一個(gè)較優(yōu)的安排。還是會(huì)有一個(gè)點(diǎn)過(guò)不了。隨機(jī)調(diào)整的部分在此基礎(chǔ)上，每次在第1類任務(wù)中隨機(jī)選擇兩個(gè)任務(wù)，交換它們的位置。再在第2類任務(wù)中隨機(jī)選擇兩個(gè)任務(wù)交換它們的位置。如果算出的答案比原來(lái)優(yōu)，那么就接受這種調(diào)整。

即使交換2000次左右，依然很快。均分紙牌有N堆紙牌，編號(hào)分別為1，2，…，n。每堆上有若干張,但紙牌總數(shù)必為n的倍數(shù).可以在任一堆上取若干張紙牌,然后移動(dòng)。移牌的規(guī)則為：在編號(hào)為1上取的紙牌，只能移到編號(hào)為2的堆上；在編號(hào)為n的堆上取的紙牌，只能移到編號(hào)為n-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。SampleInput498176SampleOutput6貪心按照從左到右的順序移動(dòng)紙牌。如果第i堆的紙牌數(shù)不等于平均值v：1．若a[i]>v，則將a[i]-v張從第i堆移動(dòng)到第i+1堆；2．若a[i]<v，則將v-a[i]張從第i+1堆移動(dòng)到第i堆。若n=3，三堆紙牌數(shù)分別為為1，2，21的話，v=8,那么讓第一堆的紙牌數(shù)達(dá)到8的時(shí)候，需要從第二堆拿7張過(guò)來(lái)，此時(shí)第二堆的紙牌數(shù)是-5。這樣很奇怪嘛？其實(shí)我們只是改變了移動(dòng)牌的順序而已，而算出的最小操作次數(shù)是正確的。我們一定可以通過(guò)調(diào)整操作的順序，使得每堆的牌數(shù)任何時(shí)候都大于等于零，比如每次只考慮將牌數(shù)大于v的牌堆的牌移到相鄰位置（這樣的操作一定存在）。NOIP2010提高組第三題簡(jiǎn)要題意：給你n個(gè)點(diǎn)，有些點(diǎn)之間有帶權(quán)邊，你要把這些點(diǎn)分為兩個(gè)集合，使得兩個(gè)端點(diǎn)在同一集合中的邊的最大邊權(quán)盡量小。二分答案，用二分圖判斷是否合法這樣是O(nlogn)的有沒(méi)有接近O(n)的做法？能貪心嗎？如何貪心？假設(shè)題目一開(kāi)始就把邊按照邊權(quán)從大到小排序了。從大到小考慮每一條邊enemy-friend并查集這道題網(wǎng)上有很多題解，這里就不細(xì)講了SGU246請(qǐng)問(wèn)，在一個(gè)長(zhǎng)度為P的圓環(huán)的整點(diǎn)上最多能夠放置多少個(gè)1，使得所有的1之間在圓環(huán)上的距離都不為Q.1<=Q<=P<=10^18將那些整點(diǎn)標(biāo)號(hào)為0~P-1.如果我們?cè)?處放置一個(gè)1，那么Q處便不能夠放置1了，于是根據(jù)貪心的思想，我們?cè)?*Q處放置一個(gè)1....。如果這樣能夠把所有的位置都確定，那么答案就是Pdiv2。如果P與Q不互質(zhì)，那么這樣做是不能確定所有位置的。比如P=12，Q=3.考慮有幾個(gè)這樣的不相關(guān)的部分。應(yīng)該是有g(shù)cd(P,Q)個(gè)的，而且每個(gè)部分的長(zhǎng)度都是P/gcd(P,Q).所以答案就是gcd(P,Q)*(P/gcd(P,Q)div2)變成回文串給你一個(gè)小寫(xiě)字母組成的字符串，長(zhǎng)度為N。每次操作，你可以交換串中相鄰的兩個(gè)字符。請(qǐng)你使用最少的操作次數(shù)，讓字符串變成一個(gè)回文串。如果有解則輸出最少操作次數(shù)，如果無(wú)解輸出WTF.1<=N<=10^6看到這么大的數(shù)據(jù)范圍，驚呆了，感覺(jué)應(yīng)該是類似貪心的做法。最多只允許一種字符的出現(xiàn)次數(shù)是奇數(shù)，且它會(huì)出現(xiàn)在最中間位置。否則無(wú)解。如果有出現(xiàn)奇數(shù)次的字符，先將這種字符的排在最中間的那個(gè)（比如有7個(gè)這種字符，就選第4個(gè)）移到整個(gè)串的最中間去。然后如果對(duì)于某種字符，在串的左半邊的數(shù)量跟在串的右半邊的數(shù)量不等，則進(jìn)行跨越中線的調(diào)整（調(diào)整時(shí)你可以讓左半邊的的一個(gè)調(diào)整到右半邊去（剛調(diào)整到中間字符的右邊就可以了），再讓右半邊的一個(gè)到左邊去，這樣交替調(diào)整...其實(shí)你也可以讓所有需要從左邊調(diào)整到右邊去的先調(diào)整，但要注意由于此時(shí)原來(lái)中間那個(gè)字符的位置可能就不在中線上了，所以你需要調(diào)整到的位置是原來(lái)中間那個(gè)字符的位置的右邊的相鄰位置，而不一定是‘跨越中線’。）事實(shí)上不管用這里說(shuō)的哪種方法調(diào)整，都是最優(yōu)的。接下來(lái)，我們可以只調(diào)整左半邊。先使得左半邊最左的字符等于右半邊最右的字符..然后再使左半邊第二左的字符等于右半邊第二右的字符...這樣一定是最優(yōu)的。如果只要求輸出答案，也可以考慮上課時(shí)說(shuō)的‘求逆序?qū)€(gè)數(shù)’的方法。不過(guò)直接調(diào)整，得到的結(jié)果也是一樣的。SGU296給你一個(gè)有N位的數(shù)n，你需要?jiǎng)h去其中P位，并使得剩下的數(shù)盡量大。1<=P<N<=1000選取的最高位只能是原數(shù)的1~N–P+1位我們應(yīng)該選取其中最大的數(shù)如果有多個(gè)最大的數(shù)，選取位置最靠前的（也就是高位）次高位的方法類似，注意要保證當(dāng)前已經(jīng)刪的數(shù)不能超過(guò)題目要求。SGU165給你n個(gè)數(shù)a[1]..a[n],其中-50<=a[i]<=50對(duì)每個(gè)i都成立。且sigma{a[i](i=1~