n688 - pC. 卡牌遊戲
題目描述
題目給定 N 張卡牌，每張卡牌都有一個數值，以及 K 次魔法機會。每次魔法可以改變卡牌的正負號。目標是找到最佳的魔法使用策略，使得卡牌總和最大。必須使用完所有的 K 次魔法。
解題思路
解題思路是貪婪地將魔法施放在絕對值最小的負數上，直到負數用完。如果 K 仍然大於負數的數量，則將剩餘的魔法施放在正數上，每次選擇絕對值最小的正數，並將其變成負數。如果 K-負數數量是奇數，則需要額外將一個絕對值最小的正數變成負數兩次，相當於不變。
首先，對卡牌數值進行排序。然後，計算負數的數量。如果 K 小於等於負數的數量，則將魔法施放在前 K 個負數上，將它們變成正數。否則，將魔法施放在所有負數上，然後將剩餘的魔法施放在正數上。如果剩餘魔法數量為奇數，則將絕對值最小的正數變成負數兩次，相當於沒有改變。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
int n, k, sum = 0;
cin >> n >> k;
int a[n], ct = 0, mi=0x7fffffff;
for (int i = 0; i < n; i++) {
cin >> a[i];
if(a[i] < 0) ++ct;
mi = min(mi, abs(a[i]));
}
sort(a, a + n);
if(k <= ct){
for(int i = 0; i < k; i++) sum -= a[i];
for(int i = k; i < n; i++) sum += a[i];
cout << sum ;
}
else{
for(int i = 0; i < ct; i++) sum -= a[i];
for(int i = ct; i < n; i++) sum += a[i];
if((k - ct) % 2) sum -= 2 * mi;
cout << sum ;
}
return 0;
}