首先让我们先学一下二分答案这个东西...
二分答案,肯定与二分有关,还与可能是答案的东西有关...
二分答案的准确定义:
二分答案是指在答案具有单调性的前提下,利用二分的思想枚举答案,将求解问题转化为验证结果。
大体流程:
首先需要估计答案的上下界,然后不断取区间中点进行验证(这就要求答案的验证应当简单可行),并通过验证结果不断更新答案区间,最终得到答案。不难看出,朴素的枚举验证时间复杂度是O(n)的,而二分可以做到O(logn)
二分答案的特征:
1.答案具有单调性
2.二分答案的问题往往有固定的问法,比如:令最大值最小(最小值最大),求满足条件的最大(小)值等。
二分答案的写法:
1.在单调递增序列a中查找 >= x 的数中最小的一个(即x 或 x的后继):
while (l < r) {
int mid = (l + r) >> ;
if (a[mid] >= x) r = mid;
else l = mid + ;
}
return a[l];
后继
2.在单调递增序列a中查找 <= x 的数中最大的一个(即x 或 x的前驱):
while (l < r) {
int mid = (l + r + ) >> ;
if (a[mid] <= x) l = mid;
else r = mid - ;
}
return a[l];
前驱
关于这两段代码的解释(见下图):
下面这是一个二分答案的模板题(2019 pdoi T3):
https://www.luogu.org/problemnew/show/P2678
这是一个二分答案的模板,然后二分答案的题的细节实在是太多了!!!(然后就一直wa ,无法列举..
(在不知道有二分答案这个东西之前发现自己的思路完全与其相反,自己只是暴力地解出答案,而不是二分枚举答案
二分答案的核心上面也都讲了,下面直接是AC代码外加部分细节解释:
#include <cstdio> inline int get_num(){
int num = ;
char c = getchar();
while (c < '' || c > '') c = getchar();
while (c >= '' && c <= '')
num = num * + c - '', c = getchar();
return num;
}//快读 const int maxn = 5e4 + ; int stone[maxn], n, m, L; inline int check(int x){
int cnt = , last = ;
for(int i = ; i <= n; i++){
if(stone[i] - stone[last] < x) cnt++;
//留着这块石头发现最短路径小于mid,则要删去
else last = i;//留着则更新上一块石头坐标
}
if(cnt <= m) return ;//是否合法
else return ;
}//检查是否合法 int main(){
L = get_num(), n = get_num(), m = get_num();
for(int i = ; i <= n; i++) stone[i] = get_num();
int l = , r = L;//@1
while(l < r){
int mid = (l + r + ) >> ;//@2
if(check(mid)) l = mid;
else r = mid - ;
}//二分答案的核心
printf("%d", l);
return ;
}
AC代码