| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P186SUMG - ROUND 6G - Đánh dấu mảng số |
Cho một mảng A[] có kích thước N. Một phần tử có thể đánh đấu dược khi mà nó lớn hơn cả phần tử liền trước và liền sau của nó (nếu có tồn tại).
Ví dụ, với mảng {4, 9, 1, 3}; “9” và “3” là các phần tử có thể đánh dấu.
Trên mảng, ta có thể thực hiện 1 thao tác: thao tác này lựa chọn 1 phần tử trên mảng và giảm nó đi 1 đơn vị.
Hãy cho biết, với 1 <= k <= ceil(N/2); với ceil(x) là số x được làm tròn lên thành số nguyên (ví dụ: ceil(0.4) = 1); ta cần thực hiện ít nhất bao nhiêu thao tác để có thể đánh dấu được k phần tử?
Input
Dòng đầu tiên chứa một số nguyên N (1 <= N <= 5000), chỉ kích thước mảng A[].
Dòng thứ hai chứa N số nguyên A_i, là các phần tử của A[] (1 <= A_i <= 10^5).
Output
In ra ceil(N/2) số nguyên, cách nhau bằng dấu cách. Số thứ i biểu diễn số thao tác ít nhất cần thực hiện lên mảng để có thể đánh dấu được i phần tử trên mảng.
Example
Input: 5 1 1 1 1 1 Output: 1 2 2
Input: 3 1 2 3 Output: 0 2
Input: 5 1 2 3 2 2 Output: 0 1 3
| Được gửi lên bởi: | adm |
| Ngày: | 2018-08-11 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
