2018年藍橋杯省賽B組 第十題 乘積最大

給定N個整數A1, A2, … AN。請你從中選出K個數，使其乘積最大。

請你求出最大的乘積，由于乘積可能超出整型範圍，你隻需輸出乘積除以1000000009的餘數。

注意，如果X<0， 我們定義X除以1000000009的餘數是負(-X)除以1000000009的餘數。

即：0-((0-x) % 1000000009)

【輸入格式】

第一行包含兩個整數N和K。

以下N行每行一個整數Ai。

對于40%的資料，1 <= K <= N <= 100

對于60%的資料，1 <= K <= 1000

對于100%的資料，1 <= K <= N <= 100000 -100000 <= Ai <= 100000

【輸出格式】

一個整數，表示答案。

【輸入樣例】

5 3

-100000

-10000

2

100000

10000

【輸出樣例】

999100009

再例如：

【輸入樣例】

5 3

-100000

-100000

-2

-100000

-100000

【輸出樣例】

-999999829

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多餘内容。

注意：

main函數需要傳回0;

隻使用ANSI C/ANSI C++ 标準;

不要調用依賴于編譯環境或作業系統的特殊函數。

所有依賴的函數必須明确地在源檔案中 #include

不能通過工程設定而省略常用頭檔案。

送出程式時，注意選擇所期望的語言類型和編譯器類型。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const int MOD = 1e9 + 9;
int n, k;

ll a[N];
int cnt[3];
ll ans;

bool cmp(int a, int b) {
	return abs(a) > abs(b);
}

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
		if (a[i] > 0) cnt[0]++;
		else if (a[i] == 0) cnt[2]++;
		else cnt[1]++;
	}
	sort(a, a + n,cmp);//按絕對值從大到小排序，我們隻選前面k個數 k<=n n = 1e5
	ans = 1;
	if (cnt[0] == n) {//全是正數
		for (int i = 0; i < k; i++) {//選前k個
			ans = (ans % MOD) * (a[i] % MOD) % MOD;
		}
	}
	else if (cnt[1] == n) {//全是負數
		if (k & 1) {//如果k是奇數，那麼答案必是負數，我們要負數盡可能小
			for (int i = n - 1; i >=n - k; i--) {//倒着取
				ans = (ans % MOD) * (a[i] % MOD) % MOD;
			}
		}
		else {//偶數個負數，那麼答案為整數，就要負數盡可能大
			for (int i = 0; i < k; i++) {//
				ans = (ans % MOD) * (a[i] % MOD) % MOD;
			}
		}
	}
	else if (cnt[2] > n - k) {//如果必須取到0
		ans = 0;
	}
	else if (cnt[2] > 0 && cnt[2] == n - k && cnt[1] & 1) {//如果0的個數等于n-k個，而且剩下的數有奇數個負數，那麼也隻能為0
		ans = 0;
	}
	else {//一般情況
		//由于已經按絕對值從大到小排序了，是以要保證答案最大，隻需要前k個數乘積盡量是正數
		ll ne_cnt = 0;//求出前k個數負數的個數
		int jc;
		for (int i = 0; i < k; i++) {
			if (a[i] < 0) ne_cnt++;
		}
		if (ne_cnt & 1) {//如果前k個數中有奇數個負數，乘積就為負數，那麼就要從k~n-1中選一個較大的正數替換前面較小的負數，或者從k~n-1中選一個較大的負數，替換前面較小的正數。
			ll bpn[2],snn[2],bnn[2],spn[2];
			bool f[4] = {0,0,0,0};
			for (int i = k-1; i >= 0; i--) {//找最小的負數
				if (a[i] < 0) {
					snn[0] = a[i];
					snn[1] = i;
					f[0] = 1;
					break;
				}
			}
			for (int i = k; i < n; i++) {//找比最小的負數大或者相等的正數
				if (a[i] > 0 ) {
					bpn[0] = a[i];
					bpn[1] = i;
					f[1] = 1;
					break;
				}
			}
			if (f[0] && f[1]) {//如果找到一個小負數和一個大整數進行交換
				jc = 1;
			}

			for (int i = k - 1; i >= 0; i--) {//找最小的正數
				if (a[i] > 0) {
					spn[0] = a[i];
					spn[1] = i;
					f[2] = 1;
					break;
				}
			}
			for (int i = k; i < n; i++) {//找比最小的正數大或等的負數
				if (a[i] < 0) {
					bnn[0] = a[i];
					bnn[1] = i;
					f[3] = 1;
					break;
				}
			}
			if (f[2] && f[3]) {
				if (abs(bnn[0]) > abs(bpn[0])) {
					jc = 2;
				}
			}
			if (jc == 1) {
				a[snn[1]] = bpn[0];
			}
			else if (jc == 2) {
				a[spn[1]] = bnn[0];
			}
			for (int i = 0; i < k; i++) {
				ans = (ans %MOD) * (a[i] % MOD) % MOD;
			}
		}
		else {//前k個數中有偶數個負數，那麼乘起來一定為正
			for (int i = 0; i < k; i++) {
				ans = (ans %MOD) * (a[i] % MOD) % MOD;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}