CSES - Increasing Array | Dãy tăng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , SPyofgame , Namlenam
Dạng bài
Điểm: 900 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một mảng gồm \(n\) số nguyên dương. Bạn cần biến đổi sao cho mảng này được sắp xếp theo trình tự tăng dần, và mọi phần tử trong mảng đều không nhỏ hơn phần tử đứng trước.

Trong mỗi lần biến đổi, bạn có thể tăng một phần tử lên một đơn vị. Hãy tìm số lần biến đổi ít nhất để thoả mản điều kiện trên.

Input

  • Dòng đầu chỉ chứa số nguyên dương n là độ dài của mảng.
  • Dòng thứ hai gồm n số nguyên dương \(x_1, x_2, \ldots, x_n\), là các phần tử của mảng.

Output

  • In ra số lần biến đổi ít nhất.

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
5

Bình luận

  • NguyễnTiếnHưng • 10:41 p.m. 23 Tháng 3, 2025 • 
    ll solve(vector<ll>& arr, ll N) {
    ll ans = 0;
    for (ll i = 1; i < N; i++) {
        if (arr[i] < arr[i - 1]) {
            ans += (arr[i - 1] - arr[i]);
            arr[i] = arr[i - 1]; 
        }
    }
    return ans;
}
    0
    Phản hồi
    • WAGKENTA • 2:55 p.m. 9 Tháng 11, 2024 •

      include <bits/stdc++.h>

      using namespace std;
      long long n,a[1000000],i,s,dem;
      int main()
      {
      cin>>n;s=0;
      for(i=1;i<=n;i++)
      {
      cin>>a[i];
      }
      for(i=1;i<=n;i++)
      {
      if(a[i]<a[i-1])
      {
      dem=dem+a[i-1]-a[i];
      a[i]=a[i-1];
      }
      }
      cout<<dem;
      return 0;
      }

      0
      Phản hồi
      • vietnammuonnam_mvn • 6:03 p.m. 27 Tháng 8, 2024 •

        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))

        -4
        Phản hồi
        • penistone • 4:46 a.m. 27 Tháng 9, 2023 • ← chỉnh sửa 6

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

          -20
          Phản hồi
          • huyquang_25 • 10:29 p.m. 2 Tháng 2, 2023 • ← đã chỉnh sửa

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

            -9
            Phản hồi
            • tunangoo • 12:25 a.m. 4 Tháng 9, 2022 • ← chỉnh sửa 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)

              25
              Phản hồi