หาดัชนีที่ถูกลดเป็นศูนย์สุดท้ายหลังดำเนินการใน Python

สมมติว่าเรามีอาร์เรย์ A ขนาด n และค่า K ดำเนินการ: เริ่มจาก A[0] ถึง A[n-1] ลบ K ออกจากแต่ละสมาชิก หาก A[i] < K ตั้งเป็น 0 และไม่ดำเนินการต่อ ทำซ้ำจนกว่าทุกค่าจะเป็น 0 หาดัชนีที่กลายเป็น 0 สุดท้าย

เช่น A = [4, 3, 6, 8, 3, 10], K = 4 ผลลัพธ์คือ 5

ขั้นตอนการแก้ปัญหา (คณิตศาสตร์)

1. แปลงแต่ละ A[i] เป็นจำนวนรอบที่ต้องลบ: A[i] = ceil(A[i] / K) = (A[i] + K - 1) // K
2. หาดัชนีที่มีค่ามากที่สุด (ถ้าเท่ากันเลือกดัชนีหลังสุด)

ตัวอย่างโค้ด Python

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

อินพุต

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

เอาต์พุต

5