UVA 10747 Maximum Subsequence：貪心選擇最大乘積子序列

問題描述

給定 N 個整數（|值| ≤ 10,000），從中選出 K 個數，使其乘積最大。若乘積相同，則選擇總和最大的方案。輸出該子序列的元素和。

貪心策略

1. 按絕對值降序排序，相同絕對值時正數優先。
2. 優先選取前 K 個：若負數個數為偶數，乘積為正，直接為最優。
3. 負數為奇數時調整：需替換一個元素使負數變偶數。有兩種方案：
   • 方案 A：移除選取集合中最小的正數，加入未選集合中最大的負數（絕對值最大）。
   • 方案 B：移除選取集合中絕對值最小的負數，加入未選集合中最大的正數（或 0）。
4. 比較兩種方案：比較乘積大小（用分數比較避免溢出），乘積相同則比較總和。
5. 特殊情況處理：若選取集合包含 0，或無法調整使乘積為正，則退而求其次選擇總和最大的 K 個數（即按原值降序取前 K）。

關鍵細節

• 乘積可能極大，不能直接儲存。比較兩個方案乘積時，利用 sum1 = sum - removed + added 並比較 removed1 * added2 vs removed2 * added1 等價於比較乘積比值。
• 需仔細處理 0 的情況：若最優乘積為 0，則選總和最大的方案（即盡量選大的數，包括 0）。
• 排序比較函數：abs(a) != abs(b) ? abs(a) > abs(b) : a > b。

程式碼實現（C++）

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

const int INF = 0x3f3f3f3f;
int n, k, a[10005];

bool cmpAbs(int x, int y) {
    if (abs(x) != abs(y)) return abs(x) > abs(y);
    return x > y; // 同絕對值，正數優先
}

int solve() {
    sort(a, a + n, cmpAbs);
    int sum = 0, negCnt = 0;
    for (int i = 0; i < k; ++i) {
        sum += a[i];
        if (a[i] < 0) ++negCnt;
    }

    if (negCnt % 2 == 0) {
        // 已為正乘積，但需檢查是否含 0 導致乘積為 0
        if (a[k-1] == 0) {
            sort(a, a + n);
            sum = 0;
            for (int i = n-1; i >= n-k; --i) sum += a[i];
        }
        return sum;
    }

    // 負數為奇數，嘗試兩種替換
    int sumA = -INF, sumB = -INF;
    int remA = 0, addA = 0, remB = 0, addB = 0;

    // 方案 A：換掉一個正數，換入一個負數
    for (int i = k-1; i >= 0; --i) if (a[i] > 0) {
        for (int j = k; j < n; ++j) if (a[j] < 0) {
            sumA = sum - a[i] + a[j];
            remA = abs(a[i]); addA = abs(a[j]);
            break;
        }
        if (sumA != -INF) break;
    }

    // 方案 B：換掉一個負數，換入一個非負數
    for (int i = k-1; i >= 0; --i) if (a[i] < 0) {
        for (int j = k; j < n; ++j) if (a[j] >= 0) {
            sumB = sum - a[i] + a[j];
            remB = abs(a[i]); addB = abs(a[j]);
            break;
        }
        if (sumB != -INF) break;
    }

    // 處理無法替換或替換涉及 0 的情況
    if (addB == 0 && sumA == -INF) { // 只能換入 0 且無方案 A
        sort(a, a + n);
        sum = 0;
        bool hasZero = false;
        for (int i = n-1; i > n-k; --i) {
            if (a[i] == 0) hasZero = true;
            sum += a[i];
        }
        if (hasZero) sum += a[n-k];
        return sum;
    }
    if (sumA == -INF && sumB == -INF) { // 兩種方案都不可行
        sort(a, a + n);
        sum = 0;
        for (int i = n-1; i >= n-k; --i) sum += a[i];
        return sum;
    }
    if (sumA == -INF) return sumB;
    if (sumB == -INF) return sumA;

    // 比較乘積：addA/remA vs addB/remB  <=> addA*remB vs addB*remA
    long long prodCmp = 1LL * addA * remB - 1LL * addB * remA;
    if (prodCmp == 0) return max(sumA, sumB);
    return (prodCmp > 0) ? sumA : sumB;
}

int main() {
    while (cin >> n >> k, n || k) {
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << solve() << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(N log N) —— 排序主導，N ≤ 10,000。
• 空間：O(N)。

總結

本題是貪心策略與細節處理的經典結合。核心在於「按絕對值排序優先取大」，並通過有限的替換操作將負數個數調整為偶數。關鍵難點在於乘積溢出的避免（用分數比較）以及 0 邊界情況的完備處理。