ACM，大学最开始接触的，也是让我学到最多的东西，至此还没有忘记。记得当初寒假一个人默默地学习C语言，从变量，从函数。回到学校后，看着同学都在游戏之中，而自己每天默默地切题，有时还比他们还要晚。可是付出了，不一定有回报，比赛是一个团队，不是单靠个人，虽然我们的个人能力是没有问题的，但是，ACM还要靠RP。哈哈。。。总结下，主要还是自己的基础不够扎实，不够深入理解，只是知道这道题目怎么AC了，就草草地结束了，没有总结，没有透彻的吃进去。
无聊之际，得把以前学的都总结下，为了留下足迹，为了养成学到什么总结什么的好习惯。不是有说男人20几岁就要开始养成写作的习惯嘛。以前学的算法都基本上忘得差不多了，以前放在网易Blog中的一些文章，在此拿出来继续看看，可能会觉得不一样的意境。也可以再次充实下自己。
关于求极值，很多时候利用数学知识还是可以很好解决的，不过人是懒的，可以不用大脑，就不用了，什么事情都可以让计算机去实现。如果要用数学方法的话，求导还是可以求出最大值，最小值的，不过定义域范围什么的，有时会比较恶心。还是用我们的计算机来实现吧。让计算机来计算极值。
二分法，其中二分好像比较熟悉吧，对的，二分查找？查找用二分的话，那么时间复杂度可以降低到O(log2n)。不断地去逼近我们要找的那个值。比如已经排序好的
a[9] = {1，2，3，4，5，6，7，8，9}。
如果我们要查找6，一般情况下，我们是从1，2，3。。。这样慢慢找下去的。不过用二分的话，
l=0，r=8，m=(l+r)/2=4，a[m] = 5
发现5比6小，所以应该在m-r这个范围内，接着
l=4, r=8, m=(l+r)/2=6，a[m]=7,
比较发现7比6大，所以这个值应该在l-m之间，即a[4]-a[6]之间，然后再次下去，就找到了6。就这么简单。而二分求极值，其实和这个差不多，只是他加进了函数，判断的条件不比较mid这个值和所要找的值。具体来看看下面这道题目吧。
xmu 1214.购物
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submissions: 263 (60 users) Accepted: 68 (49 users)
[ My Solution ]
Description
为了组织班级聚会，wlnwyyfc来到新华都购买一种物品，这类物品的价值为P。他身上有N笔款项，每笔款项都有相应的价值。他希望使用这些款项至少要买M件这类物品，但是款项必须要单独使用，即不能合在一起去购买。问物品的价值P（必须为正整数）最大能为多少？
Input
第一行输入两个整数N(1<=N<=100,000)，M(1<=M<=1,000,000,000)。
接下来输入N个正整数ai(1<=ai<=1,000,000,000)，表示N笔款项的价值。
Output
输出一个数，表示P的最大值。如果没有满足的值，输出-1。
Sample Input
3 4
10 5 2
Sample Output
3
Source
wlnwyyfc@xmu
这个题目就是对价值p进行二分求最大值
#include <stdio.h>
int main()
{
int n, m, a[100001], i, sum = 0;
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if(sum < a[i]) sum = a[i];//先求出最大的款项
}
int l = 1, r = sum, mid; 最大的价值p肯定是1到这最大的款项之间。
while(1) //下面也可以算作是二分的框架吧
{
mid = (l + r) / 2;
int cnt = 0;
for(i = 0; i < n; i++)
cnt += a[i] / mid; //表示最多可以买的件数
if(l >= r-1) //这里表示已经二分完了
{
if(cnt >= m){printf("%d\n", mid); break;} //表明有这个最大值
else {printf("-1\n"); break;}
}
if(cnt >= m)l = mid; 这个和二分查找没什么区别吧？
else if(cnt < m) r = mid;
}
return 0;
}
二分还是比较简单的，因为我们都学过二分查找，也就是折半查找，不过还有三分法，哈哈，这个三分法一开始我还没有十分明白。到点吃饭了，唉，通货膨胀，物价就这么涨了，吃个饭也这么贵。吃完再来分析分析三分法求极值问题吧。。。。