_二分+贪心_
#include<bits/stdc++.h>
using namespace std;
int a[50010];
int w , n , m;
bool check(int mid){ //可行解 mid扮演了最小值
int ant = 0;
int pos = 0; //从左往右遍历的过程
for(int i = 1 ; i <= n + 1; i++){
if(a[i] - a[pos] < mid ){
ant ++ ;
}
else{
pos = i;
}
}
if(ant > m){
return false;
}
else
return true;
}
int main()
{
cin >> w >> n >>m;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
}
a[n+1] = w;
int l = 0, r = w ;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)){
l = mid;
}
else
r = mid - 1;
}
cout << l ;
return 0;
}
换个模板r=mid怎么就不行了
对于一个单增的序列,这个东西它要找最大值,也就是说一开始这个可行解肯定先去mid的右边区间去找就要打这个板子。
感谢大佬指点