NETWRKNB SPOJ – PREVNOI 2013-2014

ĐỀ BÀI: NETWRKNB

CODE: NETWRKNB

PERIODNB SPOJ – PREVNOI 2013-2014

ĐỀ 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.

CODE: PERIODNB

ACMNB SPOJ – PREVNOI 2013-2014

ĐỀ BÀI: ACMNB

SOLUTION:

Thuật toán có thể suy ra từ cách làm thực tế. Nếu Tí làm tất cả 2n bài sẽ mất tổng thời gian là

Tuy nhiên Tí phải nhường lại n bài cho Tèo. Mỗi khi Tí nhường bài i cho Tèo, thời gian S sẽ giảm đi một lượng ci = ai – bi. Ta cần chọn n bài để Tí nhường cho Tèo sao cho thời gian S giảm đi nhiều nhất, tức là phải chọn n chỉ số i có c lớn nhất.

CODE: ACMNB