[Buổi 1][Tư duy giải bài & Độ phức tạp][WS] Bài 1: Hiệu chỉnh dãy đo
Hiệu chỉnh dãy đo
Bối cảnh và bài toán
Một dây chuyền theo dõi mức hiệu chuẩn của n mốc cảm biến theo thứ tự thời gian. Do sai số đọc thấp, một số mốc có thể nhỏ hơn mốc ngay trước đó. Hệ thống hậu xử lý chỉ chấp nhận một dãy không giảm, tức a[i] >= a[i-1] với mọi i > 1.
Kỹ thuật viên chỉ được tăng giá trị của một mốc lên 1 trong một thao tác; không được giảm bất kỳ giá trị nào. Vì mỗi đơn vị hiệu chỉnh đều có chi phí, cần dùng ít thao tác nhất có thể.
Yêu cầu
Tính số thao tác tăng tối thiểu để dãy sau hiệu chỉnh trở thành dãy không giảm.
Input
- Dòng 1: số nguyên
n. - Dòng 2:
nsố nguyêna[1], a[2], ..., a[n].
Output
Một số nguyên duy nhất — số thao tác tối thiểu.
Ràng buộc
1 <= n <= 2 * 10^50 <= a[i] <= 10^9
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 20% | n ≤ 20, 0 ≤ a[i] ≤ 100 | 01–04 |
| S2 | 30% | n ≤ 2 000, 0 ≤ a[i] ≤ 10^6 | 05–10 |
| S3 | 50% | Không có ràng buộc bổ sung | 11–20 |
Ví dụ 1
Input
5
3 2 5 1 7
Output
5
Giải thích. Mốc thứ 2 phải tăng từ 2 lên 3, tốn 1 thao tác. Sau đó mốc thứ 4 phải tăng từ 1 lên 5, tốn 4 thao tác. Dãy có thể trở thành 3 3 5 5 7, tổng cộng 5 thao tác.
Ví dụ 2
Input
4
1 2 2 10
Output
0
Giải thích. Dãy đã không giảm nên hệ thống không cần hiệu chỉnh.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M01-B01-WS01 |
| Buổi | B01 |
| Loại bài | WORKSHOP |
| Mức độ khó | Trung bình (Medium) |
| Thời gian làm bài khuyến nghị | 20 phút |
| Time limit | 1 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++17 |
Nguồn: Phỏng theo CSES Problem Set — Increasing Array (Task 1094).
Tham khảo: https://cses.fi/problemset/task/1094/
Ghi chú biên tập: Biên tập lại ngữ cảnh/constraints và chuẩn hóa theo lộ trình FULLHOUSE DEV; giữ bản chất yêu cầu của bài nguồn.
Comments