ZeroJudge 解題筆記：f461.現金兌換點卷

作者：王一哲
日期：2026年10月2日


ZeroJudge 題目連結：f461.現金兌換點卷

解題想法

題目的意思是要從 $n$ 個數字之中，任選 $2$ 個數字相減、取絕對值，將所有組合得到的絕對值相加即為答案。但是這題的 $n$ 最大為 $100,000$，如果真的取 $2$ 個一組，組合數高達 $4,999,950,000$，硬算絕對會超時，需要找數學規律。

假設 $n$ 個數字儲存為陣列 $nums$，且數字由小到大排序，其中 $nums[i]$ 在答案之中，會被 $n - (i+1)$ 個比 $nums[i]$ 大的數字各減 $1$ 次，而 $nums[i]$ 則會對 $i$ 個比自己小的數各減 $1$ 次，因此 $nums[i]$ 對答案的貢獻為 $$ nums[i] \times [-(n-i-1)] + nums[i] \times i = nums[i] \times (2i + 1 - n) $$ 可以推論答案 $$ ans = \sum_{i = 0}^{n-1} nums[i] \times (2i + 1 - n) $$ 答案可能很大，如果用 C++ 解題記得要用 long long，否則會溢位。

這題另一個要注意的地方在於測資量極大，雖然記憶體上限為 512 MB，但是用 Python 解題時，如果用 sys.stdin.read().split() 一次讀取所有測資，並用 sys.stdout.write() 一次輸出所有答案，在最後一筆測資會遇到 MemoryError。我後來改用生成器及 next，每次只轉換一個整數，處理完一筆測資就輸出，最後一筆測資 5.9 s、24.8 MB 過關。。

Python 程式碼

通過 75% 的測資，最後一筆測資 MemoryError。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        nums = sorted(map(int, data[ptr : ptr + n]))
        ptr += n
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 5.9 s，記憶體約為 25.2 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield part

    tokens = get_tokens()
    
    while True:
        try:
            n = int(next(tokens))
        except StopIteration:
            break
        
        nums = [int(next(tokens)) for _ in range(n)]
        nums.sort()
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 1.4 s，記憶體約為 4.5 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        vector<LL> nums(n);
        for(int i = 0; i < n; i++) {
            scanf("%lld", &nums[i]);
        }
        sort(nums.begin(), nums.end());
        LL ans = 0LL;
        for(LL i = 0; i < n; i++) {
            ans += (2*i + 1 - n) * nums[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

使用時間約為 1.2 s，記憶體約為 4.5 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        vector<LL> nums(n);
        for(int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        sort(nums.begin(), nums.end());
        LL ans = 0LL;
        for(LL i = 0; i < n; i++) {
            ans += (2*i + 1 - n) * nums[i];
        }
        cout << ans << "\n";
    }
    return 0;
}