CSES - Increasing Array | Dãy tăng
Xem PDF
Đ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
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;
}
4 bình luận nữa