思路分析:要求母牛跳跃最短距离的最大值.暴力的判断肯定不行,复杂度太高.因为每个石头间的距离已知,我们可以通过距离来判断石头是否可以放的下.所以二分法寻找最小距离,然后判断即可.
#include<iostream> #include<algorithm> using namespace std; const int maxsize = 50000 +10; int dis[maxsize],l,n,m,ans,mid; int judge(int x) { // 最小距离为x int last = 0; int num = n - m;//减掉m个石头 int cur;//放置num个石头，循环num次 for(int i = 0; i < num; i++) { //对于这些石头，要使任意间距不小于x cur = last + 1;//当前石头的编号 while(cur<=n&&(dis[cur]-dis[last]<x)) {//>=x才能放石头 cur++;//不满足,则继续判断下一个. } if(cur>n) {//如果石头总数大于n了,则说明距离过大了,能放置的石头太少. return 0; } last = cur;//更新上一块石头的编号.继续判断下一个石头是否可以放置.. } return 1; } int main() { cin>>l>>n>>m; for(int i = 1; i <= n; i++) { cin>>dis[i]; } if(n==m) { cout<<l<<endl;//如果移除的石头数和拥有的石头数相同,则最小距离就是l return 0; } dis[0] = 0; dis[n+1] = l; sort(dis,dis+n+2); int right = l,left = 0; while(left<=right){//二分的模板.. mid = (left+right) / 2; if(judge(mid)){ left = mid+1; ans = mid; }else{ right =mid-1; } } cout<<ans<<endl; return 0; }
