TOINCSEQ - Non-decreasing sequence
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một dãy số a 1 , a 2 , …, a n . 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 ≤ 10 5 .
- Các phần tử của dãy số là số tự nhiên không vượt quá 10 9 .
- Trong 50% số test, N không vượt quá 10 3.
- Người up: voj
- Nguồn bài: VNOI Marathon 2009 - Warm up Round