首页 > 试题广场 >

孙悟空的徒弟

[编程题]孙悟空的徒弟
  • 热度指数：3778 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

打败魔人布欧以后，孙悟空收了n个徒弟，每个徒弟战斗力各不相同。他教导所有的徒弟和体术，合体后战斗力为原战斗力相乘。任何两个徒弟都可以合体，所以一共有n*(n-1)/2种合体徒弟。有一天，他想考验一下孙悟天战斗力如何，希望在所有n*(n-1)/2种合体徒弟中选择战斗力第k高的，与孙悟天对战。可是孙悟空徒弟太多了，他已然懵逼，于是找到了你，请你帮他找到对的人。


输入描述:
第一行两个int。徒弟数量：n <= 1*10^6；战斗力排名:k <= n*(n-1)/2
第二行空格分隔n个int，表示每个徒弟的战斗力。


输出描述:
战斗力排名k的合体徒弟战斗力。
示例1

输入

5 2
1 3 4 5 9

输出

36
算法知识视频讲解
添加回答
Java
御坂10096头像 御坂10096 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long k = scan.nextLong();
        
        long[] power = new long[n];
        for(int i=0;i<n;i++){
            power[i] = scan.nextLong();
        }
        Arrays.sort(power);
        long l = 1,r = power[n-1]*power[n-2],mid = 0;
        while(l<r){
            mid = (l+r+1)/2;
            long cnt = 0;
            int left = 0, right = n-1;
            while(left<right && cnt<k){
                while(power[left]*power[right]<mid) left++;
                cnt+=Math.max(right-left,0);
                right--;
            }
            if(cnt>=k) l=mid;
            else r = mid-1;
        }
         System.out.println(l);
    }
}
借鉴大佬们二分思路的Java版本，可以通过。
这道题我的问题就是陷入思维定式，只考虑如何优化剪枝候选的值，没有把他放到[1,power[n-1]*power[n-2]]这一连续区间中考虑
编辑于 2020-07-28 11:13:31 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 哔哩哔哩 测试工程师 PHP工程师 查找 穷举 2019 Java工程师
来自：哔哩哔哩 2019秋招...
上传者：小小
难度：
1条回答 9545浏览

热门推荐

通过挑战的用户

查看代码

相关试题

孙悟空的徒弟

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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