ZeroJudge 解題筆記：t164.連續成績

作者：王一哲
日期：2026年11月1日


ZeroJudge 題目連結：t164.連續成績

解題想法

每組測資第一列為一個整數 $n ~(1 \leq n \leq 2 \times 10^5)$，代表有 $n$ 場比賽；第二列有 $n$ 個整數 $a_i ~(-10^9 \leq a_i \leq 10^9)$，分別代表第 $i$ 場比賽的成績變化。找出一段非空連續區間，使這段區間的成績變化總和最大，並輸出該總和。

這題是連續區間最大和問題，很適合用滑動視窗 (sliding window) 解題。假設連續區間最大和為 $imax$，目前區間和為 $curr$，兩者預設值皆為第 0 場比賽的分數變化 $arr[0]$；視窗左端點 $left = 0$。用一個 for 迴圈更新視窗右端點 $right = 0$ 到 $n-1$，先更新 $curr += arr[right]$，再用一層 while 迴圈試著移除 $arr[left] \leq 0$ 的項目，使區間加總 $curr$ 盡量變大。如果跑完內層的 while 迴圈之後，$curr < arr[right]$，則改成以 $right$ 為新的區間起點，$curr = arr[right]$，$left = right$。for 迴圈最後才更新 $imax$。跑完 for 迴圈之後輸出 $imax$。

Python 程式碼

使用時間約為 11 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取  n 場比賽的分數
        n = int(data[ptr])
        ptr += 1
        arr = tuple(map(int, data[ptr : ptr + n]))
        ptr += n
    
        # 用滑動視窗找連續區間加總最大值 imax
        # 目前的區間加總 curr，兩者皆預設為 arr[0]
        imax = curr = arr[0]
        left = 0
        for right in range(1, n):
            curr += arr[right]
            # 試著移除左端點小於、等於 0 的項目
            while left < right and arr[left] <= 0:
                curr -= arr[left]
                left += 1
            # 如果 curr 小於 arr[right]，以 right 為新的區間起點
            if curr <= arr[right]:
                curr = arr[right]
                left = right
            imax = max(imax, curr)
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：453. Minimum Moves to Equal Array Elements

作者：王一哲
日期：2026年11月1日


LeetCode 題目連結：453. Minimum Moves to Equal Array Elements

解題想法

中等難度題。題目給一個長度為 $n$ 的陣列 $nums$，每次操作可以將陣列中 $n-1$ 項各加上 $1$，至少要操作幾次才能夠讓陣列中每一項都一樣大？

這題考數學。如果原來的陣列中最小值為 $imin$，加總為 $isum$，假設要操作 $m$ 次，則陣列加總變成 $$ isum + m \times (n-1) = n \times (imin + m) \Rightarrow m = isum - n \times imin $$ 這題用 Python 或 C++ 都可以一行解。

Python 程式碼

Runtime: 1 ms, beats 89.24%. Memory: 20.34 MB, beats 87.24%.

class Solution:
    def minMoves(self, nums: list[int]) -> int:
        return sum(nums) - len(nums) * min(nums)

Runtime: 7 ms, beats 52.32%. Memory: 20.34 MB, beats 87.24%.

class Solution:
    def minMoves(self, nums: list[int]) -> int:
        isum, imin = 0, float('inf')
        for num in nums:
            isum += num
            if num < imin:
                imin = num
        return isum - imin * len(nums)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 31.80 MB, beats 99.75%.

class Solution {
public:
    int minMoves(vector<int>& nums) {
        return accumulate(nums.begin(), nums.end(), 0) - nums.size() * (*min_element(nums.begin(), nums.end()));
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 31.90 MB, beats 97.11%.

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = (int)nums.size(), imin = INT_MAX;
        long isum = 0;
        for(int num : nums) {
            isum += num;
            if (num < imin) imin = num;
        }
        return isum - n * imin;
    }
};