题目描述

关系

内容

给定 $N$ 个整数 $A_1,A_2,\dots A_N$。

请你从中选出 $K$ 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$ 的余数。

注意，如果 $X<0$，我们定义 $X$ 除以 $1000000009$ 的余数是负 ($-X$)除以 $1000000009$ 的余数，即：$0-((0-x)\mathrm{\%}1000000009)$

输入格式

第一行包含两个整数 $N$ 和 $K$。

以下 $N$ 行每行一个整数 $A_i$。

输出格式

输出一个整数，表示答案。

数据范围

$1\le K\le N\le {10}^5$,
$-{10}^5\le A_i\le {10}^5$

输入样例 1：

5 3
-100000
-10000
2
100000
10000

输出样例 1：

999100009

输入样例 2：

5 3
-100000
-100000
-2
-100000
-100000

输出样例 2：

-999999829

问题分析

最初思路

很显然，矛盾点就是有的时候负数的绝对值是很大的。但是选了负数又如何保证最后答案尽可能为正数呢？

什么时候选择的数最后只能为负数？

我们倾向于选择绝对值尽可能大的数，所以有如下流程：

1. 如果当前结果为负数，那么下一个数只能为负数；
2. 如果当前结果为正数，那么下一个数就选绝对值最大的数；
3. 如果到了最后一个数，都无法凑为正数，那么我们就认为结果只能为负数；

为了更好的选择绝对值尽可能大的数，所以首先需要对数组进行排序。然后找出正负数的分界点；然后开始遍历。

思路分析

要对 k 进行分类讨论：

• k==n，所有数都要选；
• k < n：
  • k 是偶数，结果必然存在是非负的：
    • 负数是偶数个；
    • 负数是奇数个。我们可以将绝对值最小的负数抛弃；
  • k 是奇数，结果是正是负，完全取决于最大的那个数是正数还是负数：
    • 所有数都是负数：${\displaystyle \text{res}<0}$；
    • 至少存在一个非负数：${\displaystyle \text{res}\ge 0}$；因为，我可以选择最大的那个非负数，这样，情况就变为了 k 位偶数的情况，而我们已经证明了 k 为偶数的情况必定存在正结果；

由上述分析可知，当 k 为奇数的时候，我们可以先选择一个最大值，然后让问题转换为 k 为偶数的情况，这样就极大的简化了实现。

现在来考虑如何选择 k 为偶数的情况。为了保证结果的最大值，我们必须两个两个地选择。从左右两边向中间逼近。只有同时选择两个负数，才能保证负数的个数为奇数。

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 1000000009;
int n, k;
int a[N];

int main()
{
    scanf("%d%d", &n, &k);
    
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    sort(a, a + n);
    
    ll res = 1;
    int l = 0, r = n - 1, sigh = 1;
    if (k % 2) {
        res = a[r--];
        if (res < 0) sigh = -1;
        k--;
    }
    while (k) {
        ll x = (ll) a[l] * a[l + 1], y = (ll) a[r] * a[r - 1];
        if (x * sigh > y * sigh) {
            res = x % mod * res % mod;
            l += 2;
        } else {
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }
    printf("%lld", res);
    return 0;
}