UVA 10747 - Maximum Subsequence (貪心 + 情況討論)

問題描述

給 n 個整數，選 k 個使乘積最大；若乘積相同，使和最大。輸出該最大和。n≤10000。

核心觀察

按絕對值降序排序。前 k 個為候選集。根據負數個數奇偶、是否含 0、剩餘元素符號分類討論。

決策邏輯

1. 候選集含 0 → 乘積為 0，為使和最大，直接取數值最大的 k 個（含 0）。
2. 候選集負數個數為偶數 → 已是最優，直接輸出和。
3. 候選集負數個數為奇數 → 需調整：用候選集外元素替換候選集內某元素，使負數變偶數且乘積盡量大（絕對值盡量大）。四種子情況：
   • 候選集無正數（全負或負+0）：若外部有正數，用最小正數替換絕對值最小的負數；否則乘積必為負或 0，取數值最大的 k 個（即絕對值最小的 k 個負數）。
   • 候選集有正數：比較兩種替換方案：
     1. 用外部最小正數替換內部絕對值最小負數。
     2. 用外部絕對值最大負數替換內部最小正數。
     選乘積增益較大者（比較 outPos * inNegMinAbs vs outNegMaxAbs * inPosMin）。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
int n,k,a[MAXN];
bool cmpAbs(int x,int y){ return abs(x)!=abs(y)?abs(x)>abs(y):x>y; }

int solve() {
    sort(a,a+n,cmpAbs);
    int sum=0, negCnt=0, minNeg=0, maxPos=0;
    bool hasZero=false;
    for(int i=0;i());
        int s=0; for(int i=0;i0 && !outPos) outPos=a[i];
        if(a[i]<0 && !outNeg) outNeg=a[i];
        if(a[i]==0) hasOutZero=1;
    }
    if(maxPos==0) { // 候選集無正數
        if(outPos) return sum - minNeg + outPos;
        else { sort(a,a+n,greater()); int s=0; for(int i=0;i()); int s=0; for(int i=0;i= outNeg * minNeg) return sum - minNeg + outPos;
            else return sum - maxPos + outNeg;
        }
    }
}

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

關鍵點

• 絕對值排序確保候選集乘積絕對值最大。
• 負數奇偶性決定乘積正負，調整策略以最小代價翻轉符號。
• 邊界情況（全負、含零、無外部替換元素）需仔細處理。