n688. pC. 卡牌遊戲
標籤 : Greedy
通過比率 : 42人/49人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-15 21:35

內容

現在有 N 張數值介於 -10000 ~ 10000 的卡牌,你將可以得到所有卡牌的總和做為收益。

好消息是你有 K 次機會,可以選定一張卡牌施放魔法,改變該卡牌正負號
也就是由正改負,或由負改正。
當然你也可以將部分魔法集中施放在同張卡牌,則對同張卡牌所施放的魔法兩兩間將互相抵銷。

壞消息是這 K 次魔法都必須確實施放完畢
也就是即使原本卡牌就已經是正值了,仍必須將 K 次魔法集中或分散施放在某幾張卡牌上。

舉例來說假設 N = 3、K = 1,且三張卡牌分別為 2, 1, 3,
則最佳策略為將魔法施放在數字 1 的卡牌,最大總收益將為 2 + (-1) + 3 = 4。

請協助撰寫一個程式計算最佳策略下,可以得到的最大總收益為何。

輸入說明

第一行有兩個正整數 N 和 K,代表有 N 張卡牌和 K 次魔法需施放
1 ≤ N ≤ 10000
1 ≤ K ≤ N

第二行有 N 個整數 ai,代表第 i 張卡牌原始數字
-10000 ≤ ai ≤ 10000

輸出說明

最佳策略下,可以得到的最大總收益

範例輸入 #1
3 1
2 1 3
範例輸出 #1
4
測資資訊:
記憶體限制: 512 MB
提示 :

10%:K = 1
30%:所有 ai 皆為非負整數
60%:無特別限制 

標籤:
Greedy
出處:
113學年度hgsh校內賽 [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
41331 gallen.yes@g ... (王冠侖) n688
Python 詳解
108 2024-07-17 16:05