题解 | #孙悟空的徒弟#

孙悟空的徒弟

https://www.nowcoder.com/practice/7b841a840db64f5ebec77f6ee7e307e2

解题思路

这是一道查找第 $k$ 大合体战斗力的题目，主要思路如下：

问题分析：
- $n$ 个徒弟可以两两合体
- 合体后战斗力为原战斗力相乘
- 需要找到第 $k$ 大的合体战斗力
解决方案：
- 先对原始战斗力排序
- 使用二分查找确定第 $k$ 大的值
- 对每个二分的中值，使用双指针统计大于该值的合体数量
双指针技巧：
- 左指针从小到大遍历
- 右指针从大到小遍历
- 统计乘积大于目标值的组合数量

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    
    // 读入数据
    long long n, k;
    cin >> n >> k;
    vector<int> power(n);
    for(auto& p : power) {
        cin >> p;
    }
    
    // 排序
    sort(power.begin(), power.end());
    
    // 二分查找
    long long left = 1;
    long long right = power[n-1] * power[n-2];  // 最大可能值
    
    while(left < right) {
        long long mid = (left + right + 1) / 2;
        long long count = 0;
        
        // 双指针统计
        int i = 0, j = n - 1;
        while(i < j && count < k) {
            while(i < j && power[i] * power[j] < mid) {
                i++;
            }
            count += j - i;
            j--;
        }
        
        if(count >= k) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    cout << left << endl;
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        
        // 读入战斗力
        int[] power = new int[n];
        for(int i = 0; i < n; i++) {
            power[i] = sc.nextInt();
        }
        
        // 排序
        Arrays.sort(power);
        
        // 二分查找
        long left = 1;
        long right = (long)power[n-1] * power[n-2];
        
        while(left < right) {
            long mid = (left + right + 1) / 2;
            long count = 0;
            
            // 双指针统计
            int i = 0, j = n - 1;
            while(i < j && count < k) {
                while(i < j && (long)power[i] * power[j] < mid) {
                    i++;
                }
                count += j - i;
                j--;
            }
            
            if(count >= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        System.out.println(left);
    }
}

def find_kth_largest_power(n, k, power):
    # 排序
    power.sort()
    
    # 二分查找
    left, right = 1, power[-1] * power[-2]
    
    while left < right:
        mid = (left + right + 1) // 2
        count = 0
        
        # 双指针统计
        i, j = 0, n - 1
        while i < j and count < k:
            while i < j and power[i] * power[j] < mid:
                i += 1
            count += j - i
            j -= 1
        
        if count >= k:
            left = mid
        else:
            right = mid - 1
    
    return left

def main():
    n, k = map(int, input().split())
    power = list(map(int, input().split()))
    result = find_kth_largest_power(n, k, power)
    print(result)

if __name__ == "__main__":
    main()