Link Sub: http://www.spoj.com/PTIT/problems/PTIT125F/
Người Gửi: Sai
- Problem:
Có N (1<=N<=25,000) người leo lên và leo xuông trên 1 ngọn núi. Người i mất U(i) thời gian leo lên và D(i) thời gian để leo xuống. Trong một thời điểm chỉ có tối đa người 1 người có thể lên và tối đa 1 người có thể xuống (có thể 1 ng lên, 1 ng xuống). Những người khác có thể đứng chờ ở đỉnh ngọn núi. Thứ tự đi xuống có thể khác thứ tự đi lên. Bạn hãy xác định xem thời gian tối thiểu để cho N người lên và xuống ngọn núi là bao nhiêu.Input
- Dòng 1: Số nguyên N
- Dòng 2..1+N: Dòng i+1 chứa 2 số U(i) và D(i) (1 <= U(i) , D(i) <= 50,000).
Output
- Thởi gian tối thiểu có thể.
Example:
- Thởi gian tối thiểu có thể.
Input
3
6 4
8 1
2 3
Output:
17
- Solution:
Giải thích: đi lên và xuống theo thứ tự người 3->1->2Tính tổng time đi lên, tổng time đi xuống tương ứng với Tìm time_min đi xuống, time_min đi lên và xét xem tổng nào lớn hơn thì đó là cách đi tối ưu.
Vì tất cả mọi người cũng chỉ được 1 người lên và một người xuống thì time của nó luôn là time của người lớn hơn.