solution.md

# 乘积最大

给定 N 个整数 A1,A2,…AN。

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

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

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

**输入格式**

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

以下 N 行每行一个整数 Ai。

**输出格式**

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

**数据范围**

```
1≤K≤N≤105,
−105≤Ai≤105
```

**输入样例1：**

```
5 3
-100000
-10000
2
100000
10000
```
**输出样例1：**

```
999100009
```
**输入样例2：**

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

**输出样例2：**

```
-999999829
```

以下选项<span style="color:red">错误</span>的是？

## aop

### before

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

### after

```c

```

## 答案

```c
#define ll long long
#define inf 0x7fffffff
const int N = 1e5 + 10;
const int mod = 1e9 + 9;
int n, k;
int a[N];
ll ans = 1;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    sort(a + 1, a + n + 1);

    int sign = 1;
    if (k % 2)
    {
        ans = a[n];
        n--;
        k--;
    }

    int i = 0, j = n;
    while (k)
    {
        ll tmp1 = (ll)a[i] * a[i + 1], tmp2 = (ll)a[j] * a[j - 1];
        if (tmp1 * sign > tmp2 * sign)
        {
            ans = (tmp1 % mod * ans) % mod;
            i += 2;
        }
        else
        {
            ans = (tmp2 % mod * ans) % mod;
            j -= 2;
        }
        k -= 2;
    }

    printf("%lld\n", ans);
    return 0;
}

```
## 选项


### A

```c
#define mem(a, b) memset(a, b, sizeof(a))
#define mod 1000000009

typedef long long ll;
const int maxn = 1e6 + 5;
const double esp = 1e-7;
const int ff = 0x3f3f3f3f;
map<int, int>::iterator it;

struct node
{
    ll x;
    int f;
} a[maxn];

int n, k;

bool cmp(node x, node y)
{
    return x.x > y.x;
}

ll solve(int o)
{
    ll ans = 1;
    int cnt = 0;
    if (o == 0)
    {
        for (int i = 1; i <= k; i++)
        {
            ans = (ans * a[i].x) % mod;
            if (a[i].f == 1)
                cnt++;
        }
    }
    else
    {
        for (int i = n; i > n - k; i--)
        {
            ans = (ans * a[i].x) % mod;
            if (a[i].f == 1)
                cnt++;
        }
    }

    if (cnt & 1)
        return ans * (-1);
    return ans;
}

int main()
{
    cin >> n >> k;

    int flag = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i].x);
        if (a[i].x < 0)
        {
            a[i].f = 1;
            a[i].x = -a[i].x;
            cnt++;
        }
        else if (a[i].x > 0)
            a[i].f = 0;
        else
        {
            i--;
            n--;
            flag = 1;
        }
    }

    sort(a + 1, a + n + 1, cmp);

    ll ans = 0;

    if (n < k)
        ans = 0;
    else if (cnt == n)
    {
        if (k & 1)
            ans = solve(1);
        else
            ans = solve(0);
    }
    else if (cnt == 0)
        ans = solve(0);
    else
    {
        int tmp = 0;
        for (int i = 1; i <= k; i++)
            if (a[i].f == 1)
                tmp++;

        if (tmp % 2 == 0)
            ans = solve(0);
        else
        {
            ans = -1;

            int p = -1, q = -1;
            for (int i = k + 1; i <= n; i++)
                if (a[i].f == 0)
                {
                    q = i;
                    break;
                }
            for (int i = k; i >= 1; i--)
                if (a[i].f == 1)
                {
                    p = i;
                    break;
                }

            if (p != -1 && q != -1)
            {
                swap(a[p], a[q]);
                ans = solve(0);
                swap(a[p], a[q]);
            }

            p = -1, q = -1;
            for (int i = k + 1; i <= n; i++)
                if (a[i].f == 1)
                {
                    q = i;
                    break;
                }
            for (int i = k; i >= 1; i--)
                if (a[i].f == 0)
                {
                    p = i;
                    break;
                }

            if (p != -1 && q != -1)
            {
                swap(a[p], a[q]);
                ans = max(ans, solve(0));
                swap(a[p], a[q]);
            }

            if (ans < 0)
                ans = solve(1);
        }
    }

    if (ans < 0)
        if (flag)
        {
            cout << 0 << endl;
            return 0;
        }
    cout << ans << endl;

    return 0;
}
```

### B

```c
#define mod 1000000009
const int N = 100010;
typedef long long LL;
int a[N];
int n, k;
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    LL res = 1;
    if (n == k)
    {
        for (int i = 0; i < n; i++)
        {
            res = (res * a[i]) % mod;
        }
        cout << res % mod;
        return 0;
    }

    if (a[n - 1] < 0)
    {
        if (k % 2 == 1)
        {
            for (int i = n - 1; i >= n - k; i--)
            {
                res = (res * a[i]) % mod;
            }
        }
        else
        {
            for (int i = 0; i < k; i++)
            {
                res = (res * a[i]) % mod;
            }
        }
        cout << res << endl;
        return 0;
    }

    int l = 0, r = n - 1;
    if (k % 2 == 1)
    {
        res = a[r--];
        k--;
    }
    while (k)
    {
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r] * a[r - 1];
        if (x > y)
        {
            res = x % mod * res % mod;
            l += 2;
        }
        else
        {
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }
    cout << res << endl;
    return 0;
}
```

### C

```c
int main()
{
    int n, k;
    long long ans;
    cin >> n >> k;
    vector<long long> num;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        num.push_back(temp);
    }
    sort(num.begin(), num.end());
    if (k % 2 != 0)
    {
        ans = num.back();
        k = k - 1;
        num.pop_back();
    }
    else
        ans = 1;
    while (k > 0)
    {
        if ((num[0] * num[1]) > num.at(num.size() - 1) * num.at(num.size() - 2))
        {
            ans = ans * num[0] * num[1] % 1000000009;
            num.erase(num.begin(), num.begin() + 1);
        }
        else
        {
            ans = ans * num.at(num.size() - 1) * num.at(num.size() - 2) % 1000000009;
            num.pop_back();
            num.pop_back();
        }
        k -= 2;
    }
    cout << ans;
    return 0;
}
```