算法答疑---10:河中跳房子

一、总结

一句话总结：一串数，去掉其中几个，使得剩余数之间的最短距离最长。

a、二分法，遍历判断每一个值（从起点到终点）

b、遍历每个值的过程中，判断每次剩余的数目是不是符合题目要求

c、找到解之后要继续找，因为要找最优解

1、为什么直接输出mid会错（两个代码唯一的区别就是用ans = mid记录了结果，另一个是直接用mid输出了结果）？

直接输出mid肯定不对啊
因为如果用ans记录mid的话，那个mid肯定是我们算好的答案
而直接输出mid的话，可能是正确答案后的一次，或者n的mid值
当然也可能是正确答案，像这个题

比如，当mid为5已经满足了，但是程序还会在6-11中继续寻找答案，所以这种情况下，输出ans是对的，输出mid是错的

这样表述很抽象，不知道你懂了没有

就是如果用ans记录的方式，输出的一定是正确的mid，而直接输出mid，可能因为接下来的计算让mid改变从而不是正确答案了

2、如何快速高效的看懂一段代码（也算看懂题目的思路）？

打印中间结果，就知道题目每一步在干什么了

就能知道变量表达式是什么意思了

 1 #include<iostream>
 2 #define MAXN 50010
 3 using namespace std;
 4 int a[MAXN];
 5 int l, n, m;
 6 
 7 bool find(int mid)
 8 {
 9     cout<<"mid: "<<mid<<endl;
10     int now = 0, num = 0;
11     for(int i = 1; i <= n + 1; ++ i)
12     {
13         if(a[i] - a[now] >= mid)
14         {
15             cout<<a[i]<<" "<<a[now]<<endl;
16             ++ num;//num表示剩下的石头（除第一块） 
17             now = i;
18         }        
19     }
20     cout<<num<<" "<< n - m + 1<<"    end"<<endl;
21     if(num >= n - m + 1)//num >= n - m + 1表示剩下的石头比较多，说明石头去少了，说明最短距离还不是最长，所以往二分的右边走 
22         return 1;
23     else
24         return 0;
25 } 
26 
27 int main()
28 {
29     freopen("test.txt","r",stdin); 
30     cin >> l >> n >> m;
31     for(int i = 1; i <= n; ++i)
32         cin >> a[i];
33     int le = 0, mid, ans;
34     a[n+1] = l;
35     int ri = a[n+1];
36     //测试 
37     for(int i=0;i<=n+1;i++) cout<<a[i]<<" ";cout<<endl;
38     while(le <= ri)
39     {
40         cout<<"left-right: "<<le<<" "<<ri<<endl;
41         mid = (le + ri)/2;//mid为最长可能的最短跳跃距离 
42         
43         //cout<<mid<<" "<<find(mid)<<"----------"<<endl;
44         if(find(mid))
45         {
46             ans = mid;
47             le = mid + 1;
48         }
49         else
50             ri = mid - 1;
51             
52     }
53     cout << ans << endl;
54     return 0;     
55 }

二、河中跳房子-题目描述

总时间限制:: 1000ms
内存限制:: 65536kB

描述

每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为D_i (0 < Di < L)。

在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？

输入

第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。

输出

一个整数，最长可能的最短跳跃距离。

样例输入

样例输出

提示

在移除位于2和14的两个岩石之后，最短跳跃距离为4（从17到21或从21到25）。

三、解析及代码

首先，输入一个数组，然后用二分查找。先把数组分成两半，在左边一半从第一个开始比对。如果第一个比最小距离大，移除第一个，再看第二个。。。。。。第三个。。一直到L/2个。如果移除的比预定的多，说明要缩小范围，从开头到L/4里面找；如果比预定的少，扩大范围，从MID到L/2右边半个找；如果还是大，缩小范围；如果还是小，扩大范围，一直到应该减少的和实际减少的一致，输出。

样例过程：

测试代码：

 1 #include<iostream>
 2 #define MAXN 50010
 3 using namespace std;
 4 int a[MAXN];
 5 int l, n, m;
 6 
 7 bool find(int mid)
 8 {
 9     cout<<"mid: "<<mid<<endl;
10     int now = 0, num = 0;
11     for(int i = 1; i <= n + 1; ++ i)
12     {
13         if(a[i] - a[now] >= mid)
14         {
15             cout<<a[i]<<" "<<a[now]<<endl;
16             ++ num;//num表示剩下的石头（除第一块） 
17             now = i;
18         }        
19     }
20     cout<<num<<" "<< n - m + 1<<"    end"<<endl;
21     if(num >= n - m + 1)//num >= n - m + 1表示剩下的石头比较多，说明石头去少了，说明最短距离还不是最长，所以往二分的右边走 
22         return 1;
23     else
24         return 0;
25 } 
26 
27 int main()
28 {
29     freopen("test.txt","r",stdin); 
30     cin >> l >> n >> m;
31     for(int i = 1; i <= n; ++i)
32         cin >> a[i];
33     int le = 0, mid, ans;
34     a[n+1] = l;
35     int ri = a[n+1];
36     //测试 
37     for(int i=0;i<=n+1;i++) cout<<a[i]<<" ";cout<<endl;
38     while(le <= ri)
39     {
40         cout<<"left-right: "<<le<<" "<<ri<<endl;
41         mid = (le + ri)/2;//mid为最长可能的最短跳跃距离 
42         
43         //cout<<mid<<" "<<find(mid)<<"----------"<<endl;
44         if(find(mid))
45         {
46             ans = mid;
47             le = mid + 1;
48         }
49         else
50             ri = mid - 1;
51             
52     }
53     cout << ans << endl;
54     return 0;     
55 }

AC代码：

 1 #include<iostream>
 2 #define MAXN 50010
 3 using namespace std;
 4 int a[MAXN];
 5 int l, n, m;
 6 
 7 bool find(int mid)
 8 {
 9     int now = 0, num = 0;
10     for(int i = 1; i <= n + 1; ++ i)
11     {
12         if(a[i] - a[now] >= mid)
13         {
14             ++ num;
15             now = i;
16         }        
17     }
18     if(num >= n - m + 1)
19         return 1;
20     else
21         return 0;
22 } 
23 
24 int main()
25 {
26     cin >> l >> n >> m;
27     for(int i = 1; i <= n; ++i)
28         cin >> a[i];
29     int le = 0, mid, ans;
30     a[n+1] = l;
31     int ri = a[n+1];
32     while(le <= ri)
33     {
34         mid = (le + ri)/2;//mid为最长可能的最短跳跃距离 
35         if(find(mid))
36         {
37             ans = mid;
38             le = mid + 1;
39         }
40         else
41             ri = mid - 1;
42             
43     }
44     cout << ans << endl;
45     return 0;     
46 }

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 using namespace std;
 5 int l, n, m, a[50003], ans;                     /* 定义变量 */
 6 int count( int mid )
 7 {
 8     int j = 0, x = 0;                       /* x记录删去石头数 */
 9     for ( int i = 1; i <= n + 1; i++ )
10     {
11         if ( a[i] - a[j] < mid )        /* 石头间距离如果小于枚举的，就记录并删去。 */
12             x++;
13         else j = i;                     /* 否则移动起点。 */
14     }
15     return(x);
16 }
17 
18 
19 int main()
20 {
21     scanf( "%d%d%d", &l, &n, &m );
22     for ( int i = 1; i <= n; i++ )
23         scanf( "%d", &a[i] );
24     sort( a + 1, a + 1 + n );               /* 别忘了排序。 */
25     a[n + 1] = l;                           /* 记录终点 */
26     int left = 1, right = l;
27     while ( left <= right )                 /* 开始二分。 */
28     {
29         int middle = (left + right) / 2;
30         if ( count( middle ) <= m )     /* 计数函数 */
31         {
32             ans    = middle;
33             left    = middle + 1;
34         }else right = middle - 1;
35     }
36     printf( "%d", ans );                    /* 输出 */
37     return(0);
38 }