e178 - Runningman - 翻牌挑戰
題目描述
題目給定一組數字，每個數字的正負號可以翻轉。目標是在給定的翻轉次數 k 內，最大化所有數字的總和。
解題思路
首先，將所有數字排序。然後，貪心地翻轉所有負數，直到翻轉次數用完。如果翻轉次數還剩餘，且剩餘次數為奇數，則翻轉最小的正數。最後，計算所有數字的總和。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存數字陣列)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,k;
while(cin >> n >> k){
if(n==0)cout << "0\n";
else{
long long int a[n]={0},ans=0;
for(int i=0;i<n;++i)
cin >> a[i];
sort(a,a+n);
for(int i=0;i<n&&k;++i){
if(a[i]<0){
--k;
a[i]*=-1;
}
else
break;
}
if(k%2){
long long int ma=10000000,mit=-1;
for(int i=0;i<n&&ma;++i){
if(a[i]<ma){
ma=a[i];
mit=i;
}
}
a[mit]*=-1;
}
for(int i=0;i<n;++i)
ans+=a[i];
cout << ans << "\n";
}
}
}