---
tags: 题解,算法
---

# 从入门到头秃练习赛 18 F题题解

## 题目 https://vjudge.net/contest/446091#problem/F

## 分析

先对数组排序，然后根据k的奇偶性分类

### 1. 如果k是奇数，且数组最大值是负数

那么按从大到小一个一个取即可

### 2. 如果k是偶数，或数组最大值非负

那么最大值一定非负，如果k是奇数，那先把数组最大的数取了，变成偶数的情况。然后比较最小的两个数的积与最大的两个数的积，哪边大取哪边即可。

## 参考代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int solve(int n, int a[], int k) {
    sort(a, a + n);
    int mod = 1e9+7;
    ll ret = 1;
    if (a[n-1] >= 0 || k%2 == 0) {
        if (k%2) ret = a[--n], --k;
        for (; k >= 2; n -= 2, k -= 2) {
            ll l = (ll)a[0] * a[1], r = (ll)a[n-1] * a[n-2];
            if (l < r) {
                ret = ret * (r % mod) % mod;
            } else {
                ret = ret * (l % mod) % mod;
                a += 2;
            }
        }
    } else {
        for (--n; k; --n, --k) {
            ret = ret * a[n] % mod;
            if (ret < 0) ret += mod;
        }
    }
    return (ret + mod) % mod;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << solve(n, &a[0], m) << endl;
    return 0;
}