二分答案估计是我应该早就学会，但拖到现在才去好好看的套路吧！

二分答案是指在答案具有单调性的前提下，利用二分的思想枚举答案，将求解问题转化为验证结果。首先需要估计答案的上下界，然后不断取区间中点进行验证（这就要求答案的验证应当简单可行），并通过验证结果不断更新答案区间，最终得到答案。不难看出，朴素的枚举验证时间复杂度是O(n)的，而二分可以做到O(logn)。更令人欣喜的是，二分答案的问题往往有固定的问法，比如：令最大值最小（最小值最大），求满足条件的最大（小）值等。

 

一道模板题练个手：

---

 

这几乎是最简单的二分答案模板题，在明白二分答案后，是可以做到一遍AC的。题目的问法也十分模板（求最短跳跃距离的最大值），答案是单调的，拿走的石头越多，最短跳跃距离越大。我们可以估计最大的最短跳跃距离(1<=ans<=L)。然后取区间中点，进行验证。若发现某次跳跃比这个最短跳跃距离还小，那就把这块石头拿走。总共拿走的石头数不超过M，就说明区间中点符合要求，就将区间更新为右半区间（因为要求最大的最短跳跃距离）；反之，就将区间设为左半区间。

1 #include 
      
        2  3 inline int get_num() { 4     int num = 0; 5     char c = getchar(); 6     while (c < '0' || c > '9') c = getchar(); 7     while (c >= '0' && c <= '9') 8         num = num * 10 + c - '0', c = getchar(); 9     return num;10 }11 12 const int maxn = 5e4 + 5;13 14 int L, n, m, stone[maxn];15 16 inline int check(int x) {17     int cnt = 0, last = 0;18     for (int i = 1; i <= n; ++i) {19         if (stone[i] - stone[last] < x) ++cnt;20         else last = i;21     }22     if (cnt <= m) return 1;23     else return 0;24 }25 26 int main() {27     L = get_num(), n = get_num(), m = get_num();28     for (int i = 1; i <= n; ++i) stone[i] = get_num();29     int l = 1, r = L + 1;30     while (r - l > 1) {31         int mid = l + (r - l) / 2;32         if (check(mid)) l = mid;33         else r = mid;34     }35     printf("%d", l);36     return 0;37 }