Chương trình tìm khu vực được truy cập nhiều nhất trong một đường tròn bằng Python

Giả sử chúng ta có một số n và một mảng được gọi là các vòng. Chúng ta có một đường tròn bao gồm n cung khác nhau được dán nhãn từ 1 đến n. Bây giờ hãy coi một cuộc đua sẽ được tổ chức trên đường đua này, cuộc đua bao gồm m vòng khác nhau. Vòng thứ i bắt đầu từ các vòng ngành [i - 1] và kết thúc ở các vòng ngành [i]. Ví dụ:nếu vòng 1 bắt đầu ở các vòng ngành [0] và kết thúc ở các vòng ngành [1]. Vì vậy, chúng tôi phải tìm các lĩnh vực được truy cập nhiều nhất được sắp xếp theo thứ tự tăng dần. (Các số theo dõi theo thứ tự tăng dần của số khu vực theo hướng ngược chiều kim đồng hồ)

Vì vậy, nếu đầu vào là n =4 round =[1,3,1,2], thì đầu ra sẽ là [1, 2]

bởi vì cuộc đua bắt đầu từ khu vực 1. Thứ tự của các khu vực được truy cập như sau:[1,2,3 (cuối vòng 1), 4,1 (cuối vòng 2), 2 (cuối vòng 3)]. Tại đây, cả hai khu vực 1 và 2 đều được ghé thăm hai lần và chúng là những khu vực được truy cập nhiều nhất. Và các khu vực 3 và 4 chỉ được truy cập một lần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• d:=một bản đồ mới

• đối với j trong phạm vi từ 1 đến n, thực hiện

  • d [j]:=0

• d [vòng [0]]:=1

• đối với tôi trong phạm vi từ 1 đến kích thước của các vòng - 1, thực hiện

  • nếu vòng [i]> vòng [i-1], thì

    • đối với j trong các vòng phạm vi [i-1] +1 đến các vòng [i] +1, thực hiện

      • d [j]:=d [j] + 1

  • nếu không,

    • đối với j trong các vòng phạm vi [i-1] +1 đến n, thực hiện

      • d [j]:=d [j] + 1

    • đối với j trong phạm vi 1 đến vòng [i], thực hiện

      • d [j]:=d [j] + 1

• curr:=d [vòng [0]]

• hết:=[vòng [0]]

• đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện

  • nếu tôi không giống với các vòng [0], thì

    • nếu d [i]> curr, thì

      • curr:=d [i]

      • hết:=[i]

    • ngược lại khi d [i] giống với curr thì

      • nối tôi với ra

• trả lại sau khi sắp xếp

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

4, [1,3,1,2]

Đầu ra

[1, 2]