ZeroJudge n688. pC. 卡牌遊戲

解題思路

  • 必須使用 K 次魔法把正數變成負數、負數變成正數。
  • 可對同個卡牌重複使用魔法。
  • 必須用完 K 次魔法。

可以分為以下狀況：

  1. 負數數量大於 K：
    從最小的負數開始轉換 K 次負數即可。
  2. 負數數量小於 K，且 K 減去負數數量為偶數：
    將所有負數轉為正數，正數直接加總即可（使用偶數次魔法對數值無影響）
  3. 負數數量小於 K，且 K 減去負數數量為奇數：
    將所有負數轉為正數後，需判斷要讓哪個數字轉為負數。
    負數中最大的數轉為正數後與最小的正數比大小。
    • 若後者較大，使前者轉負數
    • 若前者較大，使後者轉負數
  4. 沒有負數，且 K 為偶數：
    直接加總所有數字。
  5. 沒有負數，且 K 為基數：
    將最小的數轉為負數後加總。

程式碼

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# n688 AC

# 取得 N, K
N, K = [int(i) for i in input().split()]

# 取得 N 個數字並排序
a = sorted([int(i) for i in input().split()])

# 將負數與正數分開
am = [] # 負數
ap = [] # 正數
for number in a:
    if number < 0:
        am.append(number)
    else:
        ap.append(number)

# 計算負數的數量
am_length = len(am)

# 如果 K 小於等於負數的數量
if K <= am_length:
    for i in range(K): # 將前 K 個負數轉為正數
        am[i] = -am[i]
    ans = sum(am) + sum(ap) # 狀況 1.

# 如果 K 大於負數的數量
else:
    # 如果 K 減去負數的數量後是偶數
    # 則將所有負數轉為正數
    # 剩下的次數可兩兩抵銷
    if (K - am_length) % 2 == 0:
        ans = - sum(am) + sum(ap) # 狀況 2.、狀況 4.

    # 如果 K 減去負數的數量後是奇數
    # 且負數的數量不為 0
    # 必須從已經轉換的負數或正數中選擇一個數字轉為負數
    elif am_length:
        # 最大負數轉正後比最小正數小
        # 將最大負數轉正後再轉為負數最划算
        if -am[-1] < ap[0]:
            ans = -sum(am[:-1]) + am[-1] + sum(ap) # 狀況 3-1.

        # 最大負數轉正後比最小正數大
        # 將最小正數轉為負數最划算
        else:
            ans = -sum(am) + sum(ap[1:]) - ap[0] # 狀況 3-2.

    # 沒有負數，且 K 為奇數，則取最小正數轉為負數
    else:
        ans = sum(ap[1:]) - ap[0] # 狀況 5.

print(ans)

Python AC