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)，虽然这并不是多项式级别的算法，但在实际使用中的效果非常好。引入参数后，由于增加了一个条件，我们就可以将不确定的量变为确定的量，从而解决了问题。三． 总结 本文主要通过几个例子说明了参数搜索法在信息学中的应用，从上文的例子可以看出加入参数一方面能大大降低思维复杂度，另一方面也能得到效率相当高的算法，这使得我们解最解问题又多了一中有力的武器。当然，任何事物都是具有两面性的。参数搜索在具有多种优点的同时也有着消极的一面。由于需要不断调整参数逼近最优解，其时间复杂度往往略高于最优算法，且通常依赖于某个权值的大小，使得我们得到的有时不是严格意义上的多项式算法。文章中还总结了使用此方法解题的一般步骤，在实际应用中，我们不能拘泥于形式化的东西，必须灵活应用，大胆创新，这样才能游刃有余的解决问题。