Problem 54: Minimum Operations to Make Array Strictly Increasing
Problem Statement: Given an array of integers, determine the minimum number of increments (increasing any element by 1 per operation) required to make the array strictly increasing.
Input
The first line contains an integer n. The next line contains n space-separated integers.
Output
Print the minimum number of operations needed.
Examples
Input:
5
1 1 1 1 1
Output:
10
Solution Explanation
Iterate over the array, and whenever an element is not greater than the previous one, increment it to previous+1, and accumulate the difference. This greedy method ensures minimal operations.
Solution in C++
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
long long operations = 0;
for(int i = 1; i < n; i++){
if(a[i] <= a[i-1]){
int diff = a[i-1] + 1 - a[i];
operations += diff;
a[i] = a[i-1] + 1;
}
}
cout << operations << "\n";
return 0;
}