CSES - Increasing Array | Dãy tăng

Authors:

Problem type

Points: 900 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given an array of \(n\) integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input

The first input line contains an integer \(n\): the size of the array.
Then, the second line contains \(n\) integers \(x_1, x_2, ..., x_n\): the contents of the array.

Output

Print the minimum number of moves.

Constraints

~1 \le n \le 2 \cdot 10^5~
~1 \le x_i \le 10^9~

Example

Sample input

5
3 2 5 1 7

Sample output

Comments

def min_changes_to_non_decreasing(n, arr):
# Biến để lưu tổng số lần biến đổi cần thiết
changes = 0

# Duyệt qua mảng từ phần tử thứ hai
for i in range(1, n):
    if arr[i] < arr[i - 1]:
        # Tính số lần biến đổi cần thiết
        changes += arr[i - 1] - arr[i]
        # Cập nhật giá trị của phần tử hiện tại để không nhỏ hơn phần tử trước đó
        arr[i] = arr[i - 1]

return changes

Đọc đầu vào

n = int(input())
arr = list(map(int, input().split()))

Tính và in số lần biến đổi ít nhất

print(min_changes_to_non_decreasing(n, arr))

1 reply

-18

penistone 4:46 a.m. 27 sep, 2023 ← edit 6 →

xóa đi vì rác

This comment is hidden due to too much negative feedback. Click here to view it.

-8

huyquang_25 10:29 p.m. 2 feb, 2023 ← edited →

hihi

This comment is hidden due to too much negative feedback. Click here to view it.

25

tunangoo 12:25 a.m. 4 sep, 2022 ← edit 2 →

phần giới hạn viết sai rồi kìa (dòng 2 n, thay bằng x_i)
. Đề bài ghi là lớn hơn nhưng test thì lại là lớn hơn hoặc bằng)