题意:在青蛙的世界里有一项竞赛,要求青蛙在给定的跳跃次数M 以内跳过河。我们预先知道河宽L,河上有N块石头,青蛙可以在石头上停留。求青蛙的每次跳跃至少跳多远才能顺利过河。
题解:当青蛙跳长等于河宽L时它一定能跳过河。那么通过二分跳长,求出能过河的最短跳长。
#include <algorithm> #include <iostream> using namespace std; int L, n, m; int stone[500005]; bool success ( int jump ) /* 判断一个跳长是否能让青蛙顺利过河 */ { if ( jump * m < L ) return false; int i = 1, j = 0, cnt = 0; while ( i <= n + 1 ) { cnt++; if ( jump < stone[i] - stone[j] ) return false; while ( jump >= stone[i] - stone[j] && i <= n+1 ) i++; j = i - 1; /* 因为前一跳最远能跳到 i - 1 个石头上, 那么就把这块最远的石头作为下一跳的起点 */ } if ( cnt > m ) return false; return true; } int main() { int l, r, mid; while ( scanf("%d%d%d",&L,&n,&m) != EOF ) { stone[0] = 0; /* 把起始的河岸看做stone[0],终点河岸看做stone[n+1] */ stone[n+1] = L; for ( int i = 1; i <= n; i++ ) scanf("%d",stone+i); sort(stone+1,stone+1+n); l = 0; r = L; while ( l <= r ) { mid = ( l + r ) / 2; if ( success ( mid ) ) /* 若能顺利过河,那么尝试找一个更短的跳长,看能不能符合要求,否则找一个更大的跳长 */ r = mid - 1; else l = mid + 1; } printf("%d\n",l); } return 0; }