Tại của hàng pizza của Mr. Hải Dương có một điểm khác biệt với các cửa hàng khác, nếu tại của hàng bình thường thì khách hàng đến trước sẽ được phục vụ trước, khách hàng đến sau sẽ được phục vụ sau thì ở của hàng Pizza của Mr. Hải Dương sẽ phục vụ theo tiêu chí thời gian đợi trung bình của khách hàng là nhỏ nhất, vì vậy Anh ta sẽ quyết định phục vụ khách hàng nào trước chứ không phụ thuộc vào khách đến sớm hay muộn.
Mỗi loại bánh pizza khác nhau thì cần một khoảng thời gian khác nhau để làm bánh. Vì chỉ có một lò nướng bánh nên trong thời gian nướng một chiếc bánh pizza này thì Anh ta không thể nướng thêm chiếc bánh nào khác.
Ví dụ: Nếu cửa hàng có khách đến vào các thời điểm và yêu cầu chiếc bánh pizza có thời gian làm bánh là . Nếu theo tiêu chí khách đến trước được phục vụ trước thì thời gian chờ đợi của ba khách hàng lần lượt là . Như vậy thời gian chờ trung bình là . Đây không phải là phương án tối ưu theo tiêu chí thời gian chờ trung bình nhỏ nhất. Mr. Hải Dương sẽ lựa chọn phục vụ theo thứ tự là khách , khách và sau đó mới là khách . Khi đó thời gian chờ của ba khách lần lượt là . Như vậy thời gian chờ trung bình là .
Yêu cầu: Bạn hãy giúp Mr. Hải Dương tính thời gian chờ trung bình nhỏ nhất. Chỉ cần in ra phần nguyên của thời gian chờ trung bình nhỏ nhất.
Ghi chú:
Thời gian chờ của một khách hàng là độ chênh lệch giữa hai thời điểm: thời điểm khách hàng đến cửa hàng và thời điểm khách hàng rời cửa hàng;
Mr. Hải Dương không biết trước các yêu cầu của khách hàng, tức là đến thời điểm , khi khách hàng tới cửa hàng thì Mr. Hải Dương mới biết khách hàng yêu cầu bánh pizza làm trong thời gian .
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương là số khách hàng;
dòng tiếp theo, dòng thứ chứa hai số nguyên dương mô tả khách hàng đến của hàng vào thời điểm và chiếc bánh khách hàng cần sẽ mất thời gian làm bánh là .
Các số trên một dòng được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là phần nguyên của thời gian chờ trung bình nhỏ nhất.
Ví dụ:
Dữ liệu vào:
3
0 3
1 9
2 5
Dữ liệu ra:
8
Giải thích:
Thứ tự phục vụ là khách hàng , khách hàng và khách hàng .
Thời gian chờ trung bình nhỏ nhất là:
Dữ liệu vào:
4
0 3
20 1
1 9
2 6
Dữ liệu ra:
7
Giải thích:
Thứ tự phục vụ là khách hàng , khách hàng , khách hàng và khách hàng . Thời gian chờ trung bình nhỏ nhất là: .
