acm貪心演算法

A. 貪心演算法 活動安排問題

這道題的貪心演算法比較容易理解，我就不多說明了，只是提到一下演算法思路1、建立數學模型描述問題。我在這里將時間理解成一條直線，上面有若干個點，可能是某些活動的起始時間點，或終止時間點。在具體一下，如果編程來實現的話，將時間抽象成鏈表數組，數組下標代表其實時間，該下標對應的鏈表代表在這個時間起始的活動都有哪些，具體參照程序注釋。2、問題分解。為了安排更多的活動，那麼每次選取佔用時間最少的活動就好。那麼從一開始就選取結束時間最早的，然後尋找在這個時間點上起始的活動，以此類推就可以找出貪心解。程序代碼：#include<stdio.h>
struct inode //自定義的結構體
{
int end; //表示結束時間
inode *next; //指向下一個節點的指針
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num負責計數，i控制循環，a，b輸入時候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //輸入並建立數據結構
{
if(a==0&&b==0) break;
pt=new inode; //創建新的節點，然後將該節點插入相應的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //進行貪心演算法，i表示當前時間
{
if(start[i].next==NULL)
{
i++; //該時間無活動開始
}
else
{
int temp=10001; //臨時變數，存儲該鏈表中最早的終止時間
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //將當前時間設置成前一子問題的終止時間
num++;
}
}
printf("%d\n",num); //列印結果
return 0;
}代碼並不一定是最快速的，但是可以求出貪心解，如果你做的是ACM編程題目，不保證能AC注釋我盡力寫了，希望對你有幫助。

B. 請教做ACM的常用演算法..還是菜鳥

初期:
一.基本演算法:
(1)枚舉. (poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)
(5)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
(6)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單並查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中級:
一.基本演算法:
(1)C++的標准模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網路流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)並查集的高級應用. (poj1703,2492)
(6)KMP演算法. (poj1961,poj2406)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)

五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.

(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化演算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級:
一.基本演算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖演算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的
目的). (poj2823)
(4)左偏樹(可合並堆).
(5)後綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

Dp狀態設計與方程總結

1.不完全狀態記錄

<1>青蛙過河問題

<2>利用區間dp

2.背包類問題

<1> 0-1背包，經典問題

<2>無限背包，經典問題

<3>判定性背包問題

<4>帶附屬關系的背包問題

<5> + -1背包問題

<6>雙背包求最優值

<7>構造三角形問題

<8>帶上下界限制的背包問題(012背包)

3.線性的動態規劃問題

<1>積木游戲問題

<2>決斗（判定性問題）

<3>圓的最大多邊形問題

<4>統計單詞個數問題

<5>棋盤分割

<6>日程安排問題

<7>最小逼近問題(求出兩數之比最接近某數/兩數之和等於某數等等)

<8>方塊消除游戲(某區間可以連續消去求最大效益)

<9>資源分配問題

<10>數字三角形問題

<11>漂亮的列印

<12>郵局問題與構造答案

<13>最高積木問題

<14>兩段連續和最大

<15>2次冪和問題

<16>N個數的最大M段子段和

<17>交叉最大數問題

4.判定性問題的dp(如判定整除、判定可達性等)

<1>模K問題的dp

<2>特殊的模K問題，求最大(最小)模K的數

<3>變換數問題

5.單調性優化的動態規劃

<1>1-SUM問題

<2>2-SUM問題

<3>序列劃分問題(單調隊列優化)

6.剖分問題(多邊形剖分/石子合並/圓的剖分/乘積最大)

<1>凸多邊形的三角剖分問題

<2>乘積最大問題

<3>多邊形游戲(多邊形邊上是操作符,頂點有權值)

<4>石子合並(N^3/N^2/NLogN各種優化)

7.貪心的動態規劃

<1>最優裝載問題

<2>部分背包問題

<3>乘船問題

<4>貪心策略

<5>雙機調度問題Johnson演算法

8.狀態dp

<1>牛仔射擊問題(博弈類)

<2>哈密頓路徑的狀態dp

<3>兩支點天平平衡問題

<4>一個有向圖的最接近二部圖

9.樹型dp

<1>完美伺服器問題(每個節點有3種狀態)

<2>小胖守皇宮問題

<3>網路收費問題

<4>樹中漫遊問題

<5>樹上的博弈

<6>樹的最大獨立集問題

<7>樹的最大平衡值問題

<8>構造樹的最小環

C. acm必備知識都有哪些

備戰ACM資料
一：知識點
數據結構：
1，單，雙鏈表及循環鏈表
2，樹的表示與存儲，二叉樹（概念，遍歷）二叉樹的
應用（二叉排序樹，判定樹，博弈樹，解答樹等）
3，文件操作（從文本文件中讀入數據並輸出到文本文
件中）
4，圖（基本概念，存儲結構，圖的運算）
數學知識
1，離散數學知識的應用（如排列組合、簡單的圖論，數
理邏輯）
2，數論知識
3，線性代數
4，組合代數
5，計算幾何
二 演算法
1，排序演算法（冒拋法，插入排序，合並排序，快速排
序，堆排序）
2，查找（順序查找，二分發）
3，回溯演算法
4，遞歸演算法
5，分治演算法
6，模擬法
7，貪心法
8，簡單搜索演算法（深度優先，廣度優先），搜索中的
剪枝，A*演算法
9，動態規劃的思想及基本演算法
10，高精度運算
三、ACM競賽的題型分析
競賽的程序設計一般只有16種類型，它們分別是：
Dynamic Programming （動態規劃）
Greedy （貪心演算法）
Complete Search （窮舉搜索）
Flood Fill （不知該如何翻譯）
Shortest Path （最短路徑）
Recursive Search Techniques （回溯搜索技術）
Minimum Spanning Tree （最小生成樹）
Knapsack （背包問題）
Computational Geometry (計算幾何學)
Network Flow （網路流）
Eulerian Path （歐拉迴路）
Two-Dimensional Convex Hull （不知如何翻譯）
BigNums （大數問題）
Heuristic Search （啟發式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （雜題）
四 ACM競賽參考書
《實用演算法的分析與程序設計》 （吳文虎，王建德著，電子工業出版社，競賽類的黑寶書）
《青少年國際和全國信息學（計算機）奧林匹克競賽指導）――組合數學的演算法
和程序設計》（吳文虎，王建德著，清華大學出版社，參加競賽組合數學必學）
《計算機演算法設計與分析》 （王曉東編著，最好的數據結構教材）
《數據結構與演算法》 （傅清祥，王曉東編著，我所見過的最好的演算法教材）
《信息學奧林匹克競賽指導――1997-1998競賽試題解析》（吳文虎，王建德著，清華大學出版社）
《計算機程序設計技巧》 D.E.Kruth著，演算法書中最著名的《葵花寶典》，大師的作品，難度大）
《計算幾何》周陪德著
《ACM國際大學生程序設計競賽試題與解析（一）》 （吳文虎著，清華大學出版社）
《數學建模競賽培訓教材》 共三本 葉其孝主編
《數學模型》 第二版 姜啟源
《隨機規劃》
《模糊數學》
《數學建模入門》 徐全智
《計算機演算法設計與分析》 國防科大
五 常見的幾個網上題庫
常用網站：
1）信息學初學者之家：http://oibh.ioiforum.org/
（2）大榕樹編程世界：http://www.fjsdfz.org/~drs/program/default.asp
（3）中國教育曙光網：http://www.chinaschool.org/aosai/
（4）福建信息學奧林匹克：http://www.cfcs.com.cn/fjas/index.htm
（5）第20屆全國青少年信息學奧林匹克競賽：http://www.noi2003.org/
（6）第15屆國際青少年信息學奧林匹克競賽：http://www.ioi2003.org/
（7）全美計算機奧林匹克競賽：http://ace.delos.com/usacogate
（8）美國信息學奧林匹克競賽官方網站：http://www.usaco.org/
（9）俄羅斯Ural州立大學：http://acm.timus.ru/
（10）西班牙Valladolid大學：http://acm.uva.es/problemset
（11）ACM-ICPC：http://icpc.baylor.e/icpc/
（12）北京大學：http://acm.pku.e.cn/JudgeOnline/index.acm
（13）浙江大學：http://acm.zju.e.cn/
（14）IOI：http://olympiads.win.tue.nl/ioi/
（15）2003年江蘇省信息學奧林匹克競賽夏令營：http://jsoi.czyz.com.cn
（16）http://acm.zju.e.cn
（17）http://acm.zsu.e.cn
（18）www.shumo.com
（19）http://www.bepark.com/downldmanag/index.asp
（20）http://www.yh01.com colin_fox/colin_fox
五 如何備戰ACM/ICPC
1，個人准備（演算法書，習題集，網上做題和討論）
2，1000題=亞洲冠軍=世界決賽
3，做好資料收集和整理工作

D. acm田忌賽馬問題在線等急求！！

好暈。。田忌賽馬問題可用貪心演算法進行匹配。
我在這里借花敬佛：
http://blog.sina.com.cn/s/blog_5f0d09840100n7yx.html

E. 璋佺煡閬揂CM閮借茶繃浠涔堬紵錛堝唴閮ㄩ棶棰橈級

瀵笰CM絝炶禌鐨勭畻娉曞ぇ姒傚垎浜嗕竴涓嬬被錛屽垎鎴愪簡鏁板︺佹暟鎹緇撴瀯鍜岀畻娉曚笁澶у潡銆
涓 鏁板(Mathematics)
1 紱繪暎鏁板(Discrete Mathematics)
1.1 鍥捐(Graph Theory)
鍥劇殑閬嶅巻(Graph Traversal): DFS, BFS
鏈灝忕敓鎴愭爲(Minimum Spanning Tree): Prim, Kruskal
鏈鐭璺寰(Shortest Path): Dijkstra, Floyd
浼犻掗棴鍖(Transitive Closure)
鍏寵妭鐐(Articulation Point - UndiGraph)
鎷撴墤鎺掑簭(Topological Sort - AOV-Network)
鍏抽敭璺寰(Critical Path - AOE-Network)
鍥炶礬闂棰: 嬈ф媺璺(Euler Path), 奼夊瘑灝旈】鍥炶礬(Hamilton Tour)
宸鍒嗙害鏉(Difference Constraints): Bellman-Ford
浜岄儴鍥懼尮閰(Bipartite Matching)
緗戠粶嫻(Network Flow)
1.2 緇勫悎鏁板(Combinatorics)
2 鏁拌(Number Theory)
2.1 緔犳暟: GCD, LCM...
2.2 鍚屼綑
3 璁＄畻鍑犱綍(Computational Geometry)
綰挎電浉浜, 澶氳竟褰㈤潰縐, 鍐呯偣澶栫偣鐨勫垽鏂, 鍑稿寘(Convex Hull), 閲嶅績(Bary Center)...
4 綰挎т唬鏁
鐭╅樀(Matrix), 綰挎ф柟紼嬬粍(Linear Equations)...
5 姒傜巼璁
6 鍒濈瓑鏁板︿笌瑙ｆ瀽鍑犱綍
7 楂樼瓑鏁板
鐐圭Н(Dot Proct), 宸縐(Cross Proct), 縐鍒(Integral), 寰鍒(Differential)...
浜 鏁版嵁緇撴瀯(Data Structure)
1 綰挎х粨鏋
綰挎ц〃(Linear List)
鏍(Stack), 闃熷垪(Queue)
鏁扮粍(Array), 涓(String), 騫誇箟琛(General List)
2 闈炵嚎鎬х粨鏋
鏍(Tree)
鍫(Heap)
鍥(Graph)
3 鎺掑簭
3.1 鎻掑叆鎺掑簭
鐩存帴鎻掑叆鎺掑簭(Insert Sort) O(n^2)
鎶樺崐鎻掑叆鎺掑簭(Binary Insert Sort)
甯屽皵鎺掑簭(Shell Sort)
3.2 浜ゆ崲鎺掑簭
鍐掓場鎺掑簭(Bubble Sort) O(n^2)
蹇閫熸帓搴(Quick Sort)?? O(nlogn)
3.3 閫夋嫨鎺掑簭
鐩存帴閫夋嫨鎺掑簭(Select Sort) O(n^2)
閿︽爣璧涙帓搴(Tournament Sort) O(nlogn)
鍫嗘帓搴(Heap Sort) O(nlogn)
3.4 褰掑苟鎺掑簭(Merge Sort) O(nlogn)
3.5 鍩烘暟鎺掑簭(Radix Sort) O(d(n+radix))
4 鏌ユ壘
4.1 浜屽垎(Binary Search)
4.2 鏍戝瀷
浜屽弶鎼滅儲鏍(Binary Search Tree)
騫寵鎼滅儲鏍(AVL Tree)
騫舵煡闆(Union-Find Set)
4.3 鍝堝笇(Hashing)
涓 綆楁硶(Algorithm)
1 妯℃嫙綆楁硶
2 鎼滅儲綆楁硶
2.1 鏋氫婦鎼滅儲(Enumeration)
2.2 娣卞害浼樺厛(Depth First Search)
2.3 騫垮害浼樺厛(Breadth First Search)
2.4 鍚鍙戝紡鎼滅儲(Heuristic Search)
3 浠モ滅浉浼兼垨鐩稿悓瀛愰棶棰樷濅負鏍稿績鐨勭畻娉
3.1 閫掓帹
3.2 閫掑綊(Recursion)
3.3 璐蹇冩硶(Greedy)
3.4 鍔ㄦ佽勫垝(Dynamic Programming)

F. ACM題目求解題思路

有N個石子,每個石子重量Qi；按順序將它們裝進K個筐中；求一種方案，使得最重的筐最輕。 分析：本題乍一看很容易想到動態規劃。事實上的確可以用動態規劃解決，稍加分析我們很快得到一個簡單的演算法。用狀態f(i,k)表示將前i個石子裝入k個筐最優方案，g(i,j)表示i-j中最重的石子，則可以寫出狀態轉移方程：g(i,j)=max {g(i,j-1),Qj}f(i,j)=min max {f(k , j-1), g(k+1 , i)} | 1<=j<=k邊界條件：g(i,i)=Qi,f(1,1)=g(1,1)很明顯，這個演算法的時間復雜度為O(N3),空間復雜度為O(N2)，並不十分理想。經過一些優化可以將復雜度降為O(N2)，不過這樣思維復雜度驟然加大，且演算法本身仍不夠高效。現在已經很難在原動態規劃模型上做文章了，我們必須換一個思路。按一般的想法，順序將石子裝入筐，即先把石子放入第一筐，放到一定時候再改放第二個筐，第三個筐……但由於筐的重量沒有上限，我們無法知道放到什麼時候可以停止，轉而將石子放入下一個筐。此時，問題的難點已經顯露出來，是不是有方法可以化解呢？我們不妨針對上面的難點，加入一個參數P，改求一個判定可行解問題：每個筐石子重量和不能超過P，是否可以用K個筐裝下所有石子。首先經過分析不難發現，如果當前筐的石子總重量為T1，即將處理的石子重量為T2，若T1+T2 ≤P，則我們仍將該石子放入當前框，這是顯而易見的。由此可以得出貪心演算法，按順序把石子放進筐，若將石子放入當前筐後，筐的總重量不超過P，則繼續處理下一個石子；若重量和超過P，則將該石子放入下一個筐，若此時筐的數目超過K，則問題無解，否則處理完所有石子後就找到了一個可行解。以上演算法時間復雜度O(N),空間復雜度O(N)，這都是理論的下界。現在我們已經解決了可行解問題，再回到原問題。是不是可以利用剛才的簡化過的問題呢？答案是肯定的。一個最簡單的想法是從小到大枚舉P，不斷嘗試找最優解為P的方案（這就是剛才的可行解問題），直到找到此方案。這就是題目的最優解。估算一下上面演算法的時間復雜度。令T=∑Qi，則最壞情況下需要枚舉T次才能找到解，而每次判斷的時間復雜度為O(N)，因此總的時間復雜度為O(TN)，故需要做進一步優化。下面考慮答案所在的區間。很明顯，若我們可以找到一個總重量不超過P』的解，則我們一定能找到一個總重量不超過P』+1的解，也就是說，可行答案必定可以位於區間[q,+∞]（其中q為本題最優解）。因此，我們自然而然的聯想到了二分，具體方法為：在區間[1,T]內取中值m，若可以找到不超過m的方案，則嘗試區間[1,m-1];若不能，嘗試區間[m+1,T]。不斷重復以上步驟即可找到問題的最優解。分析一下採用二分法後演算法總的時間復雜度：由於每次除去一半的區間，則一共只需判斷log2N次，而每次判斷的時間復雜度為O(N)，因此這個演算法總的時間復雜度為O(NlgT)。一般而言，這個復雜度可以令人滿意的，並且實際使用中效果非常好。但該復雜度同權值有關，不完全屬於多項式演算法，我們可以繼續求得一個多項式演算法（該演算法與本文核心內容無關，只作簡單探討）。首先，此問題的答案必定為某一段連續石子的和，而段數不超過n2，因此，我們最多隻要判斷log2N2=2log2N次即可。現在新的問題是如何找到第m大的段。首先，以每個石子開頭的所有段，例如：3 2 1 2，以2開頭的所有段：2；2 1； 2 1 2， 由於每個石子的重量都大於0，因此總和一定是遞增的。現在有n個遞增段，如何快速的找到第k大的數呢？設各段長度為L1,L2,…,LN,中點分別為M1,M2,…,MN，我們每次詢問各段中點的大小，若L1/2+L2/2+..+LN/2>k，則找到權值最大的中點，刪去其後的數（下圖中紅色部分），否則找到權值最小的中點，刪去其前面的部分（下圖中黑色部分），可以證明刪去的一定不是所求的數。 註：上圖中每個各格子代表一個數。 由以上可知每次可以去掉某一段的1/2，因為有n段，故總共需要去O(Nlog2N)次，每次找最小最大值可以用堆實現，復雜度僅為O(lgN)，因此總的時間復雜度為O(lg2N)，而由上文我們知道找中值的操作總共有log2N次，故這個演算法的時間復雜度為O(Nlg3N)。 至此我們終於得到了一個多項式級別的演算法，當然這個演算法實現起來比較麻煩，實際效果也不甚理想，不過具有一定的理論價值，在此不做過多討論。 回顧本題解題過程，首先我們得到了一個動態規劃演算法，由於很難再提高其效率，因此我們另闢蹊徑，尋求新的演算法。在分析過程中我們發現由於筐的重量沒有上限，因此很難確定將多少石子放入同一個筐內。為了解決此難點，我們加入了參數P，改求可行解問題。參數的加入實際上就是強行給筐定了一個上界。正是由於這無形之中多出的條件，使得問題立刻簡單化，於是我們很自然的得到了貪心演算法。而最終使用二分法降低了演算法的時間復雜度，成功地解決了問題。 由上面的例子我們得到了此類解法的一般步驟，通常分為兩步：Ⅰ.首先引入參數P，解決子問題：能否找到一個不優於P的方案Ⅱ.從小到大枚舉P，判斷是否有優於P的方案，直到找出原問題的最優解 一般地，參數搜索可以通過二分法或迭代降低時間復雜度，由於迭代法證明比較復雜，所以本文更多的討論二分法。 這個方法的應用比較廣泛，通常情況下和上例一樣求最大（小）值盡量小（大）的題目都可以採用此方法，比如下面的例子。神秘的山：有n個隊員攀登n個山峰，每個隊員需要選擇一個山峰，隊員們攀登的山峰各不相同，要求最後一個登頂的隊員用的時間盡量短。 分析：本問題分為兩個部分解決：1．求出每個隊員攀登到各個山峰所需的時間；2．找一個最優分配方案。 第一部分屬於幾何問題，我們可以枚舉每個隊員攀登山峰的位置再做簡單的判斷（題目規定攀登點必須為整點，這就為枚舉提供了條件），這樣就可求得隊員們攀登上各個山峰所需的時間。下面重點討論第二部分。首先將我們的數據構圖，很明顯，我們得到的是一個二部圖，假設有3個隊員3個山峰，每個隊員攀登的時間如下 山峰1山峰2山峰3隊員1132隊員2222隊員3133 則我們可以構圖，每條邊附上相應的權值： 現在的任務就是在圖中找一個匹配，匹配中權值最大的邊盡量小。這個問題是否可以直接套用一些常見的模型呢？比如最大匹配或是最佳匹配？經過分析不難發現在這個問題中它們都是不足以勝任的，因此我們不得不做新的嘗試。 上文提到過要求極大（小）值盡量小（大）的題目往往先定出上界比較容易下手，那麼這題也採用類似的思路。引入一個參數T，先求一個判定可行解的子問題：找一個方案，要求最後登山的隊員所用時間不超過T。 改變後的題目有什麼不同之處呢？如果隊員i攀登上山峰j所需的時間超過T，則可以認為他在規定時間內不能攀登上山峰j，我們就可以把這條邊從圖中刪去。例如在上例中找一個不超過2的方案，經過一次「篩選」，保留的圖如下。 經過這次過濾保留下來的邊都是「合法邊」，我們只需要在這個新的二部圖中找一個完備匹配即可，一個完備匹配唯一對應著一個可行方案。而找完備匹配可以借用最大匹配的演算法，因為如果一個二部圖的最大匹配數等於N，則找到了一個完備匹配，否則該圖中將不存在完備匹配。（上圖中的紅色表示一個完備匹配），那麼這一步的時間復雜度為O(NM)，而在本題中M=N2，因此我們可以在O(N3)的時間內判斷出是否存在一個方案滿足最後等上山頂的隊員時間不超過T。 最後，再用二分法枚舉參數T，找到最優解。由於答案必定為某個隊員攀登上其中一個山峰的時間，因此我們開始的時候可以將所有數據排序，這樣最終的時間復雜度為O(N3lgN)。引入參數後求可行解的子問題與原問題最大的區別在於定下上界以後，我們很自然的排除了一些不可取條件，從而留下了「合法」條件，使得問題變的簡單明了。. 上面的例子在增加了上界之後，排除了一些無效條件，其實它的作用絕不僅局限於此，有些時候，它能將不確定條件變為確定條件，比如下面的例子，最大比率問題：有N道題目,每道題目有不同的分值和難度,分別為Ai,Bi；要求從某一題開始, 至少連續選K道題目,滿足分值和與難度和的比最大。 分析：最樸素的想法是枚舉下標i』,j』，得到每一個長度不小於K的連續段，通過累加Ai』->Aj』，Bi』->Bj』求出比值，並找出比最大的一段。這樣做的時間復雜度很高，由於總共有N2段，每次計算比值的時間是O(N)，則總的時間復雜度到達O(N3)，不過計算比值時，可以採用部分和優化，這樣能把復雜度降至O(N2)，但仍然不夠理想。我們需要追求更出色的演算法，先考慮一個簡單的問題——不考慮難度（Bi），僅僅要求分值和最大（當然此時分值有正有負）。這個簡化後的問題可以直接掃描，開始時為一個長度為K的段，設為Q1,Q2,…Qk， 每次添加一個新數，若Q1+Q2+..+QL-K小於0，則把它們從數列中刪去，不斷更新最優解即可。這樣我們就能在O(N)的時間內找到長度不小於k且和最大的連續段。 之所以能成功解決簡化後的問題，是由於該問題中每個量對最終結果的影響是確定的，若其小於0，則對結果產生不好的影響，反之則是有益的影響。那麼原問題每個參數對最終結果的影響是不是確定的呢？很遺憾，並不是這樣，因為每個題目有兩個不同的參數，他們之間存在著某些的聯系，而這些聯系又具有不確定性，故我們很難知道它們對最終結果是否有幫助。想解決原問題，必須設法消除這個不確定因素！那麼有沒有辦法將這些不確定的因素轉化成確定的因素呢？此時，引入參數勢在必行！那麼我們引入參數P，求一個新的問題：找一個比值不小於P的方案。這個問題實際就是求兩個下標i』,j』，滿足下面兩個不等式j』-i』+1≥k ①(Ai』+Ai』+1....+Aj』)/(Bi』+Bi』+1…+Bj』) ≥ p ②由不等式②=>Ai』+Ai』+1....+Aj』 ≥p(Bi』+Bi』+1…+Bj』)整理得(Ai』-pBi』)+(Ai』+1-pBi』+1)…+(Aj』-pBj』) ≥0可以令Ci=Ai-pBi，則根據上面不等式可知問題實際求一個長度不小於k且和大於０的連續段。由之前的分析可以知道我們能在O(N)的時間內求出長度不小於k且和最大的連續段，那麼如果該段的和大於等於０，則我們找到了一個可行解，如果和小於０，則問題無解。也就是說，我們已經能在O(N)的時間內判斷出是否存在比值不小於P的方案，那麼接下來的步驟也就順理成章了。我們需要通過二分法調整參數P，不斷逼近最優解。計算一下以上演算法的時間復雜度，設答案為T，則該演算法的時間復雜度為O(NlgT)，雖然這並不是多項式級別的演算法，但在實際使用中的效果非常好。引入參數後，由於增加了一個條件，我們就可以將不確定的量變為確定的量，從而解決了問題。三． 總結 本文主要通過幾個例子說明了參數搜索法在信息學中的應用，從上文的例子可以看出加入參數一方面能大大降低思維復雜度，另一方面也能得到效率相當高的演算法，這使得我們解最解問題又多了一中有力的武器。當然，任何事物都是具有兩面性的。參數搜索在具有多種優點的同時也有著消極的一面。由於需要不斷調整參數逼近最優解，其時間復雜度往往略高於最優演算法，且通常依賴於某個權值的大小，使得我們得到的有時不是嚴格意義上的多項式演算法。文章中還總結了使用此方法解題的一般步驟，在實際應用中，我們不能拘泥於形式化的東西，必須靈活應用，大膽創新，這樣才能游刃有餘的解決問題。