解题思路

这是一道查找第 大合体战斗力的题目,主要思路如下:

  1. 问题分析:

    • 个徒弟可以两两合体
    • 合体后战斗力为原战斗力相乘
    • 需要找到第 大的合体战斗力
  2. 解决方案:

    • 先对原始战斗力排序
    • 使用二分查找确定第 大的值
    • 对每个二分的中值,使用双指针统计大于该值的合体数量
  3. 双指针技巧:

    • 左指针从小到大遍历
    • 右指针从大到小遍历
    • 统计乘积大于目标值的组合数量

代码

#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()

算法及复杂度

  • 算法:二分查找 + 双指针
  • 时间复杂度: - 其中 是最大可能的合体战斗力
  • 空间复杂度: - 除输入数组外只需要常数空间