首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#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 &lt;stdio.h&gt; #include &lt;stdlib.h&gt; // 比较函数,用于qsort从小到大排序 int compare(const void *a, const void *b) {     long long num1 = *(long long *)a;     long long num2 = *(long long *)b;     if (num1 &lt; num2) return -1;     if (num1 &gt; num2) return 1;     return 0; } int main() {     int N, K;     scanf("%d %d", &amp;N, &amp;K);     long long *a = (long long *)malloc(N * sizeof(long long));     for (int i = 0; i &lt; N; i++) {         scanf("%lld", &amp;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 &gt; 0) {         // 计算左边一对的乘积         long long left_product = (a[left] * a[left + 1]) % MOD;         // 计算右边一对的乘积         long long right_product = (a[right] * a[right - 1]) % MOD;         // 选择乘积较大的一对         if (left_product &gt; 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>
这道题暂未补解析。