SCAU 18725 宇宙跃迁

这个是搜到的二分做法 顺便附上我的不知道哪里错了的做法 大家有兴趣看着乐呵乐呵就行(大家写题还是按照oj上的标签方法写吧)

#include
using namespace std;
int a[10005],n,k;
bool judge(int x)//判断能力x能否使飞船在k天内到达首都 
{
//	cout<<"x"<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"<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;
}

#include 
#include 
#include 
#include using namespace std;/*在基地的科学家发明“透镜”之后，宇宙航行变得更加效率。
作为基地元首的的代理人，你需要在K天内乘坐飞船到达首都川陀。
飞船可以花费一天时间，通过迁跃从一个星系到达另一个星系，但绝不能迁跃到星系之间，那样不但会遇到一些自然危险，也可能永远迷失。
我们把基地至川陀间星系的坐标看成是一个线性序列，例如a星系坐标是10，b星系坐标是15，那么飞船必须具备不小于5的迁跃能力才能从a航行至b。
基地坐标为0，请你根据基地至川陀间的N个星系坐标，计算飞船的迁跃能力至少为多大，才能在K天内（包含K天）到达川陀。
输入格式
第一行两个整数N和K。（1=
int N,K,oneday;
int a[100001];//每个星系的坐标
int b[100000];//每个星系之间的距离
//不知道哪错了 看出来的大佬指导一下
int main()
{cin>>N>>K;for(int i=0;i<N;i++)scanf("%d",&a[i]);for(int i=0;i<N-1;i++)b[i]=a[i+1]-a[i];sort(b,b+N-2);//最后一个一定为距离的最大值for(oneday=0;oneday<=a[N-1];oneday++){int ans=oneday*K;if(oneday>=b[N-2]&&ans>=a[N-1]) break;//答案有两个条件 一是大于每个星系间的最大间隙 二是在规定天数内能够到达}cout<<oneday;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！