ZeroJudge 解題筆記：a673. 10026 - Shoemaker's Problem

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


ZeroJudge 題目連結：a673. 10026 - Shoemaker's Problem

解題想法

先依照每日平均罰款金額由大到小排序，如果相同再依照讀取順序排序。

Python 程式碼

由於這題的測資有許多的空行，用 Python 解題時需要適時地跳過這些空行，導致以下的程式碼有些複雜。使用時間約為 8 ms，記憶體約為 3.3 MB，通過測試。

import sys

lines = sys.stdin.read().split('\n')
M = len(lines)
head = 0
T = int(lines[head])
head += 1
first_case = True

while T > 0:
    while head < M and lines[head].strip() == "": head += 1
    if head >= M: break
    N = int(lines[head])
    head += 1
    jobs = []
    for i in range(1, N+1):
        day, fine = map(int, lines[head].split())
        head += 1
        jobs.append((day, fine, i))
    jobs.sort(key = lambda x : (-(x[1]/x[0]), x[2]))
    if not first_case: print()
    print(" ".join([str(i) for _, _, i in jobs]))
    first_case = False
    T -= 1

改用 sys.stdin.read().split() 及 iter 可以讓程式碼比較簡潔，但是速度上反而慢了一點。使用時間約為 14 ms，記憶體約為 3.3 MB，通過測試。

import sys

result = []
lines = iter(sys.stdin.read().split())
T = int(next(lines))

for _ in range(T):
    N = int(next(lines))
    jobs = []
    for i in range(1, N+1):
        day = int(next(lines))
        fine = int(next(lines))
        jobs.append((day, fine, i))
    jobs.sort(key = lambda x : (-(x[1]/x[0]), x[2]))
    if result:  # 如果 result 已經有內容，先換行
        result.append("\n")
    res = " ".join([str(i) for _, _, i in jobs])
    result.append(f"{res}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 356 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Job {
    int day, fine, idx;
    
    Job(int a, int b, int c) : day(a), fine(b), idx(c) {}
    Job() : day(0), fine(0), idx(0) {}
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for(int t=0; t<T; t++) {
        int N; cin >> N;
        vector<Job> jobs (N);
        for(int i=0; i<N; i++) {
            cin >> jobs[i].day >> jobs[i].fine;
            jobs[i].idx = i+1;
        }
        sort(jobs.begin(), jobs.end(), [] (Job a, Job b) {
            if (a.fine*b.day == b.fine*a.day) return a.idx < b.idx;
            return a.fine*b.day > b.fine*a.day; } );
        if (t > 0) cout << "\n";
        for(int i=0; i<N; i++) cout << jobs[i].idx << " \n"[i == N-1];
    }
    return 0;
}

使用時間約為 3 ms，記憶體約為 276 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Job {
    int day, fine, idx;
    
    Job(int a, int b, int c) : day(a), fine(b), idx(c) {}
    Job() : day(0), fine(0), idx(0) {}
};

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int N; scanf("%d", &N);
        vector<Job> jobs (N);
        for(int i=0; i<N; i++) {
            scanf("%d %d", &jobs[i].day, &jobs[i].fine);
            jobs[i].idx = i+1;
        }
        sort(jobs.begin(), jobs.end(), [] (Job a, Job b) {
            if (a.fine*b.day == b.fine*a.day) return a.idx < b.idx;
            return a.fine*b.day > b.fine*a.day; } );
        if (t > 0) puts("");
        for(int i=0; i<N-1; i++) printf("%d ", jobs[i].idx);
        printf("%d\n", jobs.back().idx);
    }
    return 0;
}