| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
TOINCSEQ - Non-decreasing sequence |
| English | Tiếng Việt |
Cho một dãy số a1, a2, …, an. Bạn được thực hiện các phép biến đổi trên dãy này. Ở mỗi phép biến đổi bạn có thể chọn một giá trị bất kỳ, sau đó tăng hoặc giảm tất cả các phần tử mang giá trị đó 1 đơn vị.
Ví dụ, dãy số 1 9 9 2 2 sẽ trở thành dãy 1 9 9 3 3 nếu bạn tăng tất cả các phần tử mang giá trị 2 lên 1 đơn vị.
Yêu cầu: Hãy đếm số phép biến đổi ít nhất để dãy số đã cho là dãy không giảm.
Input
- Dòng đầu ghi số phần tử của dãy N.
- Dòng sau ghi N số tự nhiên thể hiện dãy số.
Output
- Số phép biến đổi ít nhất cần thực hiện.
Example
Input:
5
1 9 9 2 2
Output:
7
Giới hạn
- 1 ≤ N ≤ 105.
- Các phần tử của dãy số là số tự nhiên không vượt quá 109.
- Trong 50% số test, N không vượt quá 103.
ãy
| Được gửi lên bởi: | VOJ Team |
| Ngày: | 2009-07-02 |
| Thời gian chạy: | 0.200s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
| Nguồn bài: | VNOI Marathon 2009 - Warm up Round |
hide comments
|
2014-05-12 06:35:35 an IM3 Ex-Member of Bit
Chú ý tổng chi phí để biến 1 đoạn có [min, max] thành 1 giá trị có tính chất bằng nhau với mọi giá trị trong khoảng [min, max] -> có thể tham lam thay vì QHD. |
RSS