✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：蓝桥杯题解集合
📝原题地址：乘积最大
📣专栏定位：为想参加蓝桥杯的小伙伴整理常考算法题解，祝大家都能取得理想成绩！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪
问题描述
给定 N 个整数 A1,A2,…AN。
请你从中选出 K 个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。
注意，如果 X
思路
直接上结论，我们需要先对所有数字进行排序， 然后再进行判断：
情况取法结果k==n所有数都选由序列而定k k-1
个数要选且 k-1
为偶数，变为上面 k
为偶数的情况第一种情况结果一定为负数，第二种情况结果一定为非负数
所以我们可以用双指针算法，具体思路如下：
- 先对所有数进行排序。
- 如果
k为奇数，则需要将其变为偶数的情况再进行操作，同时用sign记录最终结果是正数还是负数，上面有提到过如果k是奇数需要分情况讨论，当所有数都是负数时，结果一定为负；当至少有一个数为正时，结果一定为正。所以我们只需取数组的最后一个数，判断其是否为负数即可。 - 此时，就可以按照当
k<n< code> 且 <code>k</code> 为偶数的情况进行操作，只不过要根据 <code>sign</code> 的正负来进行选取。</n<>设置一个左指针和一个右指针分别指向数组开头和结尾，然后分别取两个数相乘进行比较，由于此时的k为偶数，不会出现正负数落单的情况。 如果sign为正数，则选取相乘结果更小的；如果sign为负数，则选取相乘结果更大的，因为结果一定为负，则需要使相乘的绝对值越小越好，这样负数的绝对值越小，结果就越大。 - 输出最终结果。
; 代码
#include
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1000000009;
int a[N];
int n, k;
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
int l = 0, r = n - 1, res = 1;
int sign = 1;
if (k % 2)
{
res = a[r--];
k--;
if (res < 0) sign = -1;
}
while (k)
{
LL x = (LL)a[l] * a[l + 1], y = (LL)a[r] * a[r - 1];
if (x * sign > y * sign)
{
res = x % mod * res % mod;
l += 2;
}
else
{
res = y % mod * res % mod;
r -= 2;
}
k -= 2;
}
printf("%d\n", res);
return 0;
}
Original: https://blog.csdn.net/Newin2020/article/details/128755296
Author: Pandaconda
Title: 第九届蓝桥杯省赛 C++ B组 – 乘积最大
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/814108/
转载文章受原作者版权保护。转载请注明原作者出处！