uva 10747 - Maximum Subsequence(貪心)

題目鏈接：10747 - Maximum Subsequence

題目大意：給出n個數，從中選取k個，使得乘積最大，並且盡量使和最大。

解題思路：首先按照數的絕對值大小排序。然後就要分三大類情況討論：

（1）前k個中選到0：如果選到0的話，乘積一定是0，所以盡量選大的數，讓和變大。

（2）前k個中選到負數的個數為偶數：這樣的話直接輸出答案（一定為最優解）

（3）前k個中選到的負數個數為奇數：這類情況比較復雜，還要分成兩個子類：

a）k個中沒有正數（意味著不能用未選的數中的負數來替換）：

如果還正數：優先用正數替換最小的負數；否則注定乘積為負數或者0：選最大的k個。

b）k個中有正數：

還有正數和負數：比較最優； 只有正數：選用負數； 只有負數：選用正數； 只有0：選最大的k個，注意0一定要選。

對應的數據：

6 3 -5 -4 -3 -2 2 1

6 3 -5 -4 -3 -2 -1 0

6 3 -5 -4 -3 -2 -2 -1

6 3 5 4 -3 2 -1 1

6 3 5 -4 3 -2 1 1

6 3 5 4 -4 -2 2 1

6 3 5 4 -3 1 1 1

6 3 5 4 -3 -1 -1 -1

4 3 5 4 -3 0

答案：

-7

-3

-5

11

-1

11

10

1

9

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 10005;
int n, k, num[N];

bool cmp(const int& a, const int& b) {
	int p = abs(a), q = abs(b);
	if (p != q) return p > q;
	else return a > b;
}

void init() {
	for (int i = 0; i < n; i++) scanf("%d", &num[i]);
	sort(num, num + n, cmp);
}

int handle(int t) {
	sort(num, num + n);
	int sum = 0;
	for (int i = 1; i <= t; i++) {
		sum += num[n-i];
	}
	return sum;
}

int solve() {
	int sum = 0, cnt = 0, p = 0, q = 0;
	bool flag = false;
	for (int i = 0; i < k; i++) {
		if (num[i] == 0) {
			flag = true; break;
		} else if (num[i] < 0) {
			cnt++; q = num[i];
		} else p = num[i];
		sum += num[i];
	}
	
	if (flag) return handle(k);
	else if (cnt % 2 && k < n) {
		int x = 0, y = 0, bo = 0;
		for (int i = k; i < n; i++) if (num[i] > 0) {
			x = num[i]; break;	
		}
		for (int i = k; i < n; i++) if (num[i] < 0) {
			y = num[i]; break;
		}
		for (int i = k; i < n; i++) if (num[i] == 0) {
			bo = 1; break;
		}

		if (p == 0) {
			if (x) sum = sum - q + x;
			else sum = handle(k);
		} else {
			if (x == 0 && y == 0) sum = handle(k - 1);
			else if (x == 0) sum = sum - p + y;
			else if (y == 0) sum = sum - q + x;
			else if (x * p >= y * q) sum = sum - q + x;
			else sum = sum - p + y;
		}
	}
	return sum;
}

int main() {
	while (scanf("%d%d", &n, &k) == 2 && n + k) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}