1. 有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间

方法：桶排序

由抽屉原理知最在差值Maxsub有如下关系

所以，当所桶大小设为时，只要记录每个桶内的最大值和最小值即可。因为同一桶中的差值肯定不是最优的。

然后就成有序的了，接下来就只要比较相邻，取最优就可以了。

2.13个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球?

根据三分的思想

尽可能平均三分

4 4 5

分在4 4 5 分别记做 a4 b4 c5接下来都这样标记if(a4 == b4){		答案在c5		c5分 3 2		if(c5_3 == 比过的正常的3个)		{			找到结果是在c5_2中			找个正常的一比就完事了		}		else		{			可以得到信息，那个球是轻还是重			3个中随便找两个比较，相等则答案是另一个			不相等，则根据原先比较知道结果		}}else{	   如果不平衡，假设现在是a重b轻， 	   取a1+a2+b1放天平一边(设为左边)， 	   再取a3+a4+b2放另一边（右）， 	   若平衡，就在b3/b4任拿一个跟C1上去称就行了， 	   如果不平衡，那么假设 	   情况一：左重 	   则是a1/a2/b2有问题 	   直接把a1a2放两边称，重的那个有问题，如果平 	   衡就是b2有问题 	   情况二：右重 	   就是 a3/a4/b1有问题，方法同上}

3.给个有序数组，一个数可以由这个数组从中任取n个数求和来表示，求从1开始最小的不可表示的数？

直接上O(n)算法

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2090

设sum为1-sum内的数都可以表示，那么当sum+1>=f[i]时，就能表示1->f[i]+sum

因为1->sum都可以表示，且sum+1>=f[i] 所以f[i] + (1-sum) 都可以表示了 。

当sum = 0 时，肯定成立所以此算法成立

#include 
    
     #include 
     
      #define LL long longusing namespace std;const int mm = 1e7+9;int f[mm];LL sum;int main(){    int n,x,cas;    while(~scanf("%d",&cas))    {        while(cas--)        {            scanf("%d",&n);            sum = 0;            for(int i=0;i
     
    

4.给定二维数组，从左到右递增，从上到下递增，问x在不在数组中？

O（n*m）算法就不说了，现在说O(max(n,m))

1	2	5	8
4	7	10	14
7	11	14	18
9	12	16	19

其实应该从右上角或左下角开始选，假设这个数是7，那么8>7又因为从上到下递增，所以一整列可以舍弃，

变成子问题了。在比较 5<7 且从左到右递增，所以此行可去掉。

上代码：

#include 
    
     #include 
     
      #define LL long longusing namespace std;const int mm = 110;int n,m;int f[mm][mm];bool have(int x,int y,int z){    if(x>=n||y<0)        return false;    if(f[x][y] == z)        return true;    if(f[x][y] > z)        return have(x,y-1,z);    else if(f[x][y] < z)        return have(x+1,y,z);}int main(){    int x;    scanf("%d %d %d",&n,&m,&x);    for(int i=0;i