ĐỀ BÀI: PERIODNB
SOLUTION:
Xây dựng dãy b1,b2,…b2n-1 từ dãy a như sau:
Có thể hiểu là bi được tính bằng phần tử thứ trong dãy theo vòng tròn cộng thêm iΔ.
Dễ thấy rằng nếu HUNGNT bắt đầu từ học sinh 1 thì thời gian giờ học kéo dài là max{b[1 …n]}. Nếu bắt đầu từ học sinh 2 thì thời gian giờ học kéo dài là max{b[2 … n+1]} − Δ… Tổng quát: nếu bắt đầu từ học sinh i thì thời gian giờ học kéo dài là:
Từ đây có thể tóm tắt thuật toán như sau: Với mỗi vị trí i, ta cần nhanh chóng xác định m[i] là giá trị lớn nhất trong n phần tử tính từ bi. Khi đó đáp số là:
Sử dụng thuật toán DQUEUE để thực hiện công việc này.
Góc nhỏ của Ling 