好题

· · 个人记录

小红有 n 个互不相等的数，小明想要知道第二大的数是哪个，于是小明问了 m 个问题，就是第 a[i] 个数和第 b[i] 个数哪个更大，结果都是第 a[i] 个数比第 b[i] 个数大

小明有事先走了，你也想小红第二大的数是什么，那么最少要询问几次两个数之间的大小才能确保知道第二大的数是第几个数

数据范围： n ，m <=10^6 1000ms 512MB

输入格式：

第一行两个整数 n， m

接下来 m 行，每行两个整数 a[i] , b[i]

输出格式：

一行一个整数表示最少的询问次数

样例输入：

5 5
1 2
1 3
2 3
2 4
3 4

样例输出：

2

样例解释：

比较 1 和 5

如果 1<5 那么第一个数就是第二大的数，比较了一次

如果 1>5 那么比较 2 和 5 ，较大的那个就是第二大的数，比较了两次

为了确保能猜中第二大的数，最少需要比较 2 次

大样例输入 大样例输出

题目提交链接 题解