18725 宇宙迁跃

客官°小女子只卖身不卖艺 2023-05-21 07:05 37阅读 0赞

时间限制:1000MS 代码长度限制:10KB

题型: 编程题 语言: 不限定

## Description ##

在基地的科学家发明“透镜”之后，宇宙航行变得更加效率。  
作为基地元首的的代理人，你需要在K天内乘坐飞船到达首都川陀。  
飞船可以花费一天时间，通过迁跃从一个星系到达另一个星系，但绝不能迁跃到星系之间，那样不但会遇到一些自然危险，也可能永远迷失。  
我们把基地至川陀间星系的坐标看成是一个线性序列，例如a星系坐标是10，b星系坐标是15，那么飞船必须具备不小于5的迁跃能力才能从a航行至b。  
基地坐标为0，请你根据基地至川陀间的N个星系坐标，计算飞船的迁跃能力至少为多大，才能在K天内（包含K天）到达川陀。

## 输入格式 ##

第一行两个整数N和K。（1=<N<=10000，1=<K<=10000）  
第二行N个整数，表示N个星系的坐标ai，题目确保坐标由小到大排列。（0=<ai<=100000）

## 输出格式 ##

仅一行,飞船的最小迁跃能力。

## 输入样例 ##

5 2  
1 4 6 10 19

## 输出样例 ##

## 提示 ##

样例说明：川陀的坐标为最后一个值19。  
飞船的迁跃能力至少为10，才能在2天内到达川陀。

## 解题思路： ##

**基本思路是将跃迁能力从小到大枚举，知道发现一个跃迁能力x可以满足条件，可以知道跃迁能力是从1到an的一个序列。由于这些特征我们可以利用二分查找的方法加快找到跃迁能力x。设边界low=1,high=an；middle=(low+high)/2;看看跃迁能力是否符合题目要求（此处是一个模拟过程），如果满足的话，先记录这个能力，然后在左半区间继续探索；如果不符合要求的话，说明这个跃迁能力太小了，我们要增大这个跃迁能力，于是我们从右半区间继续探索。**  
参考代码：

#include<iostream>
    using namespace std;
    int a[10005],n,k;
    bool judge(int x)//判断能力x能否使飞船在k天内到达首都 
    { 
    // cout<<"x"<<x<<endl;
    	int i,cur_day=0,pre_pos=0;
    	for(i=1;i<=n&&cur_day<=k;i++)
    	{ 
    		if(a[i]-a[i-1]>x)
    		return false;
    		if(x>=a[i]-pre_pos)//当前能力可以走到a[i]，看看能不能走到下一个 
    		continue;
    		else
    		{ 
    			cur_day++;//时间增加一天 
    			pre_pos=a[i-1];
    		// cout<<"pre_pos"<<pre_pos<<endl;
    			i--;//回退 
    		}
    	}
    	cur_day++;//防止最后位置的时间没有加上 
    	return cur_day<=k;//判断 
    }
    int main()
    { 
    	ios::sync_with_stdio(false);
    	int i;
    	cin>>n>>k;
    	for(i=1;i<=n;i++)
    	cin>>a[i];
    	int low=1,high=a[n],middle,best=a[n];
    	while(low<=high)
    	{ 
    		middle=(low+high)/2;
    		if(judge(middle))
    		{ 
    			best=middle;//记录跃迁能力 
    			high=middle-1;//看看是否还有更小的跃迁能力也可以使其成立 
    		}
    		else
    		{ 
    			low=middle+1;
    		}
    	}
    	cout<<best;
    	return 0;
    }