题目描述

乘积最大 - 蓝桥云课 (lanqiao.cn)

题目分析

先对a[1] ~ a[n]排序

分类讨论：
1.k == n 全选

2.k < n

        ①k是偶数（结果必然非负）

                负数有偶数个（负负得正）

                负数有奇数个（只用选取偶数个即可，剩下的一个选正数）

        ②k是奇数

                所有数都是负数（答案必定小于0）

                至少存在一个非负数，取出这个非负数，将问题转化为①

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, mod = 1e9 + 9;
int n, k, a[N];
int main()
{cin >> n >> k;for(int i = 1; i <= n; i ++)cin >>a[i];sort(a + 1, a + 1 + n);int ans = 1;int l = 1, r = n;int f = 1;//正负if(k & 1)//将奇数情况转化为偶数的情况{ans = a[r];r --;k --;if(ans < 0)f = -1;//最大为负数，全为负数 } while(k){ll x = (ll)a[l] * a[l + 1], y = (ll)a[r] * a[r - 1];if(x * f > y * f){ans = x % mod * ans % mod;l += 2;}else{ans = y % mod * ans % mod;r -= 2;}k -= 2;}cout << ans;return 0;
}