首页 > 试题广场 >

赝品

[编程题]赝品
  • 热度指数：622 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了n个物品，已知其中有k个是赝品。
小红每次可以查询一个物品，她会得到一个答案，知道这个物品是不是赝品。
小红想知道，在最坏情况下，至少需要多少次查询才能找出所有赝品？
共有t次询问。

输入描述:
第一行输入一个整数t，代表用例的组数。
每行输入两个整数n和k，用空格隔开。代表一组用例。

1\leq t \leq 100
1\leq n \leq 10^9
0\leq k \leq n


输出描述:
输出t行，每行输出一个整数代表答案。
示例1

输入

3
2 1
3 2
1 1

输出

1
2
0

说明

第一组用例，两个物品有一个赝品，小红询问第一个物品，如果是赝品就直接确认了；如果不是赝品，那么赝品就是第二个物品。因此只需要一次询问。
第二组用例，三个物品有两个赝品，小红第一次询问时如果得到的答案是赝品，那么剩下两个物品需要再询问一次。
第三组用例，不需要任何询问。
算法知识视频讲解
开通博客

暂无题解

问题信息

来自：2023年蚂蚁春招技术...
难度：
3条回答 712浏览

热门推荐

相关试题

赝品

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号