猜数

[编程题]猜数

热度指数：3996 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛和妞妞正在玩一个猜数游戏，妞妞心里想两个不相等的正数，把这两个正数的和y告诉牛牛。

妞妞声称这两个数都不超过x，让牛牛猜这两个数是多少。

牛牛每猜一次，妞妞会告诉他猜对了还是猜错了，猜对了就停止游戏，猜错了就直到牛牛猜对为止。
妞妞为了加大难度，有时会误报x的大小，如果牛牛可以判断出了这个x是错误的，就会直接询问妞妞答案。
牛牛最坏情况下要猜多少次才能猜到妞妞想的数呢？

输入描述:

两个整数x，y。1<=x,y<=10¹⁴。

输出描述:

一个数n，表示牛牛在最坏情况下猜测的次数。

示例1

输入

7 10

输出

示例2

输入

4 10

输出

算法知识视频讲解

JavaScript

我教枣子简灯笼

while(line=readline()){
  line=line.split(" ")
  let x=parseInt(line[0]);
  let y=parseInt(line[1]);
  
  if(x>=y){
    print(Math.floor((y-1)/2));
  }
  
  else{
    if(y>2*x){
    print(0)
  }
    else{
      let max=Math.max(x,(y-x));
  let min=y-max
  print(Math.floor((max-min)/2)+1);
    }
    
  }
  
}

感觉在写高中数学。。。

以a b为坐标轴建立坐标系直线a+b=y 和 a=x b=x 交于 i j 两点（i<j）

即f(a)=-a+y 在[i,j]上的取值组合为答案的可行解。

分情况讨论：

1. 当x>=y 的时候

因为x>=y 所以x没什么卵用一定可以推出正确答案

i 和 j为a+b=y 与坐标轴的交点此时只需要剔除可行解中a=0 b=0（a b为正数）和a=b的时候的组合然后除以2（部分可行解对称）的情况便可。

2.当y>2x 的时候

明显x是错的输出0

3.当想x<y<2x的时候

剔除可行解中a=0 b=0（a b为正数）和a=b的时候的组合然后除以2（部分可行解对称）的情况便可。

发表于 2019-08-01 18:01:37 回复(0)