Tại sao Lists?
Như phần của đọc đầu vào, chúng ta sẽ cần đọc n số nguyên (các số nguyên cái trình bày vị trí của các
villages). Chúng ta đã làm việc với cái này một lần khi giải quyết bài toán Data Plan. Ở đó, chúng ta
sử dụng một range for loop để lặp qua chính xác n lần. Chúng ta sẽ làm cái đó ở đây.
Có một khác biệt then chốt giữa bài toán Data Plan và Village Neighborhood. Trong bài toán Data Plan, chúng
ta đọc một số nguyên, sử dụng nó, và không bao giờ tham chiếu đến nó một lần nữa. Chúng ta đã không cần giữ
nó. Nhưng trong bài toán Village Neighborhood, nó là không đủ để xem mỗi số nguyên chỉ một lần. Neighborhood
của một village phụ thuộc vào các neighbors bên trái và bên phải của nó. Không truy cập vào các neighbors đó,
chúng ta không thể tính toán kích thước neighborhood của village. Chúng ta cần lưu giữ tất cả vị trí village
cho sử dụng sau.
Cho một ví dụ về tại sao chúng ta cần lưu giữ tất cả vị trí village, xem xét test case sau:
6
20
50
4
19
15
1
Có 6 villages ở đây. Để tìm ra kích thước của neighborhood của một village, chúng ta cần các neighbors bên trái và
bên phải đó.
Village đầu tiên trong đầu vào là tại vị trí 20. Kích thước của neighborhood của village đó là gì? Để trả lời cái đó,
chúng ta cần truy cập tất cả vị trí village để rằng chúng ta có thể tìm ra các neighbors bên trái và bên phải của nó.
Quét qua các vị trí, bạn có thể nhận dạng rằng neighbor bên trái tại vị trí 19 và neighbor bên phải tại vị trí 50. Kích
thước của neighborhood của village này vì vậy là (20 – 19)/2 + (50 – 20)/2 = 15.5.
Village thứ hai trong đầu vào ở vị trí 50. Kích thước của neighborhood của village đó là gì? Lại một lần nữa, chúng ta
cần nhìn qua các vị trí để định hình nó ra. Village này tình cờ là một cái cực phải, nên chúng ta bỏ qua neighborhood của
village này.
Village thứ ba trong đầu vào là tại vị trí 4. Neighbor bên trái là tại vị trí 1, và neighbor bên phải là tại vị trí 15, nên
kích thước của neighborhood của village này là (4 – 1)/2 + (15 – 4)/2 = 7.
Village thứ tư trong đầu vào là tại vị trí 19. Neighbor bên trái là tại vị trí 15, và neighbor bên phải là tại vị trí 20, nên
kích thước của neighborhood của village này là (19 – 15)/2 + (20 – 19)/2 = 2.5.
Village còn lại duy nhất cái chúng ta cần xem xét là tại vị trí 15. Nếu bạn tính toán kích thước neighborhood của nó, bạn sẽ
nhận một câu trả lời 7.5.
So sánh tất cả các kích thước neighborhood cái chúng ta đã tính toán, chúng ta thấy rằng cái tối thiểu – câu trả lời đúng cho
test case này là 2.5.
Chúng ta cần một cách thức để lưu giữ tất cả các vị trí village để rằng chúng ta có thể tìm ra các neighbors của mỗi village.
Một string sẽ không giúp, vì string lưu giữ các kí tự, không phải số nguyên. Python lists là cứu cánh.