这道题可以用二分来解决,我们二分最短的跳跃距离,把每一个跳跃距离进行,判断在这种条约距离下,我们能够移走的石头,来和我们组委会给的石头数进行对比,最后得到一个最合适的长度;
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 5e4 +10 ; int len , n , m; int a[N] ; bool check(int x){ int num = 0 , pos = 0 ; for(int i = 1 ; i <= n ; i ++){//挨个判断,如果有a[i] 减去上一个不能移走的石头的距离, if((a[i] - pos) < x) num ++ ; //如果小于我们的跳跃距离就移走这个石头 num ++ else pos = a[i] ;//如果大于等于,那我们就不能移走这个石头 } if(num <= m) return true ; else return false ; } int main(){ cin >> len >> n >> m; for(int i = 1 ; i <= n ; i ++){ cin >> a[i] ; } int l = 0 , r = len ; while(l < r){//二分找跳跃距离 int mid = (l+r+1) >> 1 ; if(check(mid)) l = mid ; else r = mid - 1 ; } cout << l << endl ; return 0; }