在搜索Trie树内容的时候,在一个OJ答题网站“百练”看到一道题感觉还蛮有意思的,所以就自己写了一下,用java写的,下面贴出来:
描述
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
输入
两个整数,N和K
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
注意:这里发现一个问题,就是它的输出没有以农夫与牛坐标重合为标记,感觉有点不符合常规,因此我觉得它的输出应该是5.后面我的代码也是以重合为标记的,所以请注意此提示。
上代码:
package p1;
import java.util.Scanner;
public class AcmTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成的方法存根
System.out.println("输入");
Scanner in = new Scanner(System.in);
int farmer = in.nextInt();
int cow = in.nextInt();
if(farmer<0 || farmer>100000 || cow<0 || cow>100000){
System.out.println("输入无效!");
}else{
System.out.println(getMinTime(farmer,cow));
}
}
//计算最少时间
public static int getMinTime(int f, int c)
{
//如果牛的坐标小于农夫,则可以做交换便于处理,结果一致
if(f > c){
int temp;
temp = c;
c = f;
f = temp;
}
int time = 0;
int f1 = 0,f2 = 0; //f1是指先以X+1,X-1运动方式进行,f2是指先以X->2X运动方式进行
int long1,long2; //long1是指运动超过牛之后坐标差,long2是指运动后没有超过牛的坐标差
while(4*f < c){
if(2*f >c)
break;
f = 2*f; //执行x到2x的运动方式
time++;
}
if((f1 = 2*f) >c && isBeyond(f1)){
long1 = f1 - c; //超过之后的距离
long2 = long1/2; //可以进行2x运动的调整次数
if((f2 = 2*(f-long2)) <= c){
time = time+long2 + 1; //运动时间
}
}else{
f1 = 2*f;
long1 = c - f1;
long2 = long1/2;
f2 = 2*(f+long2);
time = time+long2+1;
}
//以农夫跟牛的坐标重合为成功
if(c % 2 != 0)
time++;
return time;
}
//判断农夫是否出界
public static boolean isBeyond(int f){
if(f<0 || f>100000){
return false;
}else{
return true;
}
}
}
分享到:
相关推荐
计算机算法练习题 计算机专业的算法经典 一些常用的数据结构与算法练习 很受用的
四则运算练习题含答案
(完整版)小学六年级数学练习题(解方程+简便运算).pdf
数据结构与算法经典习题 五. 求下列算法的时间复杂度。(练习题,不必交) count=0; x=1; while (x ){ x*=2; count++; } return count; 六. 求多项式A(x)的算法可根据下列两个公式之一来设计: ⑴ A(x)=anxn+an-1xn...
位运算练习题_参考答案.pdf
java练习题 大家下载看看啦 大家可以下载 看看 练习练习
对数运算练习题.pdf
计算机算法设计与分析练习题 word版 可直接打印
php算法练习题
分数乘除混合运算练习题及答案精选.doc
分数四则混合运算练习题及答案精选.doc
国科大计算机算法设计与分析的习题练习题与习题答案,分治算法,贪心算法,动态规划,回溯算法,分治限界算法,
初中数学正负数的加减乘除运算分类练习题之欧阳美创编.pdf
C语言位运算练习题1[文].pdf
蓝桥杯上的一些算法练习题,题目还算不错的
青岛版五四制五年级上册分数混合运算应用题练习题.doc
java经典算法练习题 适合初学者 内含有大量代码 包含答案 保你学完有很大的长进!
python算法练习题
运算定律及简便算法练习题.pdf
四年级运算律分类练习题.pdf