Chương trình tìm sector được ghé thăm nhiều nhất trên đường đua tròn trong Python

Giả sử ta có số n và mảng rounds. Đường đua tròn có n sector đánh số 1 đến n. Cuộc đua có m vòng. Vòng i bắt đầu tại rounds[i-1] và kết thúc tại rounds[i]. Tìm các sector được ghé thăm nhiều nhất, sắp xếp tăng dần. (Số sector tăng theo chiều ngược kim đồng hồ)

Ví dụ: n = 4, rounds = [1,3,1,2], kết quả [1, 2].

Thứ tự sector ghé thăm: [1,2,3 (kết thúc vòng 1), 4,1 (kết thúc vòng 2), 2 (kết thúc vòng 3)]. Sector 1 và 2 được ghé 2 lần, sector 3 và 4 chỉ 1 lần.

Giải thuật

1. d := {} (map sector → số lần ghé)
2. Khởi tạo d[j] = 0 cho j = 1..n
3. d[rounds[0]] = 1
4. For i từ 1 đến len(rounds)-1:
   • Nếu rounds[i] > rounds[i-1]:
     • For j từ rounds[i-1]+1 đến rounds[i]: d[j]++
   • Ngược lại (qua điểm 0):
     • For j từ rounds[i-1]+1 đến n: d[j]++
     • For j từ 1 đến rounds[i]: d[j]++
5. curr := d[rounds[0]], out := [rounds[0]]
6. For i từ 1 đến n:
   • Nếu i != rounds[0]:
     • Nếu d[i] > curr: curr = d[i], out = [i]
     • Ngược lại nếu d[i] == curr: out.append(i)
7. Trả về sorted(out)

Ví dụ (Python)

def solve(n, rounds):
    d = {}
    for j in range(1, n+1):
        d[j] = 0
    d[rounds[0]] = 1
    for i in range(1, len(rounds)):
        if rounds[i] > rounds[i-1]:
            for j in range(rounds[i-1]+1, rounds[i]+1):
                d[j] += 1
        else:
            for j in range(rounds[i-1]+1, n+1):
                d[j] += 1
            for j in range(1, rounds[i]+1):
                d[j] += 1
    curr = d[rounds[0]]
    out = [rounds[0]]
    for i in range(1, n+1):
        if i != rounds[0]:
            if d[i] > curr:
                curr = d[i]
                out = [i]
            elif d[i] == curr:
                out = out + [i]
    return sorted(out)

n = 4
rounds = [1, 3, 1, 2]
print(solve(n, rounds))

Input

4, [1,3,1,2]

Output

[1, 2]