二分（POJ-3258)

/**********
Author Smile
二分最重要的就是分析状态，在判定条件中一定要把情况考虑清楚
决定AC否
注：特别是 =
注：在写输出的时候，思考跳出来的前一个状态的符合情况的可能值
二分的答案就是前一种情况的可能值
这就需要将题目分析透彻了 
注：再写 l = mid + 1, r = mid 时 要注意那个是能更上一层楼 
https://vjudge.csgrandeur.cn/contest/477149#problem/C
**********/
#include <iostream>
#include <algorithm>using namespace std;
const int N = 5e4 + 10;
int l, n, m;
int w[N];int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> l >> n >> m;w[1] = 0;for (int i = 2; i <= n + 1; ++i){cin >> w[i];}w[n + 2] = l;sort(w + 1, w + 2 + n);int x = 0, y = l, mid, maxx = 0, r;l = x, r = y;while (l < r){mid = (l + r) / 2;int ans = 0, pos = w[1];for (int i = 2; i <= n + 2; ++i){if (w[i] - pos <= mid)ans++;else pos = w[i];	}if (ans > m)r = mid;elsel = mid + 1;		}cout << l << endl;return 0;
}