Tìm chỉ số phần tử cuối cùng trở thành 0 sau phép toán lặp trong Python

Cho mảng A n phần tử và số K. Lặp lại: từ A[0] đến A[n-1], mỗi phần tử A[i] = A[i] - K. Nếu A[i] < K thì đặt A[i] = 0 và không xử lý nữa. Tìm chỉ số phần tử cuối cùng trở thành 0.

Ví dụ: A=[4,3,6,8,3,10], K=4 → chỉ số 5 (phần tử 10).

Giải thuật (Toán học)

Số lần lặp để phần tử A[i] về 0 là ceil(A[i] / K) = (A[i] + K - 1) // K. Phần tử có số lần lặp lớn nhất (và chỉ số lớn nhất nếu bằng nhau) sẽ là phần tử cuối cùng về 0.

• Tính times[i] = (A[i] + K - 1) // K cho mọi i.
• Tìm chỉ số i có times[i] lớn nhất (ưu tiên chỉ số lớn hơn nếu bằng nhau).

Ví dụ

def search_index(A, k):
    n = len(A)
    idx = -1
    x = -10**9
    for i in range(n):
        A[i] = (A[i] + k - 1) // k
    for i in range(n):
        if A[i] >= x:
            x = A[i]
            idx = i
    return idx

arr = [4, 3, 6, 8, 3, 10]
K = 4
print(search_index(arr, K))

Đầu vào

[4, 3, 6, 8, 3, 10], 4

Đầu ra

5