赝品

[编程题]赝品

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

小红拿到了 $n$ 个物品，已知其中有 $k$ 个是赝品。
小红每次可以查询一个物品，她会得到一个答案，知道这个物品是不是赝品。
小红想知道，在最坏情况下，至少需要多少次查询才能找出所有赝品？
共有 $t$ 次询问。

输入描述:

第一行输入一个整数，代表用例的组数。
每行输入两个整数和，用空格隔开。代表一组用例。

输出描述:

输出行，每行输出一个整数代表答案。

示例1

输入

输出

1
2
0

说明

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

算法知识视频讲解

NTH_20

#include <iostream>

using namespace std;

int get(int n,int k){

if(k==n||k==0) return 0;

return n-1 ;

}

int main() {

int t;

cin>>t;

while(t--){

int n,k;

cin>>n>>k;

cout<<get(n,k)<<endl;

}

// 64 位输出请用 printf("%lld")

最后只剩下一正一假，所以n-1

发表于 2023-08-12 17:56:45 回复(1)

Java

牛客214618749号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int t = in.nextInt();
for(int i = 0; i < t; i++) {
int n = in.nextInt();
int k = in.nextInt();
if(k == 0 || n == k) {
System.out.println(0);
} else {
System.out.println(n-1);
}

}
}
}

编辑于 2025-05-03 23:40:19 回复(0)

知微见著

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int t = in.nextInt();
for (int p = 0; p < t; p++) {
int n = in.nextInt();
int k = in.nextInt();

if (k == 0 || n == k) {
System.out.println(0);
} else {
int res = Math.max(n - 1, Math.min(k, n - k));
System.out.println(res);
}

}
}
}
}

发表于 2025-04-27 22:11:30 回复(0)