简答题
偏难
#13130
乘积最大 给你两个数 N、K,从 N 个数中选出 K 个使得乘积最大。输出乘积在数学意义上对 10 9 +7 取模的值。 时间限制:1000ms,内存限制:25…
乘积最大
给你两个数 N、K,从 N 个数中选出 K 个使得乘积最大。输出乘积在数学意义上对 109+7 取模的值。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:两个整数 N、K;
第二行:N 个整数 a1、a2、……、an。
输出格式
一个整数表示答案。
输入样例#1
4 2 1 2 -3 -4
输出样例#1
12
输入样例#2
10 10 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
输出样例#2
999983200
数据范围:
1≤K≤N≤2×105,-109≤ai≤109。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <stdio.h>
#include <stdlib.h>
// 比较函数,用于qsort从小到大排序
int compare(const void *a, const void *b) {
long long num1 = *(long long *)a;
long long num2 = *(long long *)b;
if (num1 < num2) return -1;
if (num1 > num2) return 1;
return 0;
}
int main() {
int N, K;
scanf("%d %d", &N, &K);
long long *a = (long long *)malloc(N * sizeof(long long));
for (int i = 0; i < N; i++) {
scanf("%lld", &a[i]);
}
// 排序数组
qsort(a, N, sizeof(long long), compare);
const long long MOD = 1e9 + 7;
long long result = 1;
int left = 0;
int right = N - 1;
// 如果K是奇数,先取最大的元素(最右边)
if (K % 2 == 1) {
result = (result * (a[right] % MOD)) % MOD;
right--;
K--;
}
// 剩余K为偶数,每次取一对
while (K > 0) {
// 计算左边一对的乘积
long long left_product = (a[left] * a[left + 1]) % MOD;
// 计算右边一对的乘积
long long right_product = (a[right] * a[right - 1]) % MOD;
// 选择乘积较大的一对
if (left_product > right_product) {
result = (result * left_product) % MOD;
left += 2;
} else {
result = (result * right_product) % MOD;
right -= 2;
}
K -= 2;
}
// 处理结果为负数的情况(确保在0到MOD-1之间)
result = (result + MOD) % MOD;
printf("%lld\n", result);
free(a);
return 0;
}</pre><p><br/></p>
这道题暂未补解析。