解题思路
这是一道查找第 大合体战斗力的题目,主要思路如下:
-
问题分析:
个徒弟可以两两合体
- 合体后战斗力为原战斗力相乘
- 需要找到第
大的合体战斗力
-
解决方案:
- 先对原始战斗力排序
- 使用二分查找确定第
大的值
- 对每个二分的中值,使用双指针统计大于该值的合体数量
-
双指针技巧:
- 左指针从小到大遍历
- 右指针从大到小遍历
- 统计乘积大于目标值的组合数量
代码
#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()
算法及复杂度
- 算法:二分查找 + 双指针
- 时间复杂度:
- 其中
是最大可能的合体战斗力
- 空间复杂度:
- 除输入数组外只需要常数空间