問題描述
一個數組?aa?中共包含?nn?個數，問最少多少次操作，可以讓?aa?數組所有數都變成?11?。
操作的內容是：每次操作可以任選一個區間使得區間內的所有數字減?11?。 數據保證一定有解。
輸入格式
第一行一個整數?nn?表示有?nn?個整數。
第二行輸入?nn?個整數表示數組?aa?。
輸出格式
輸出一個整數表示最少操作數可以讓?aa?數組所有數字變成?11?。
樣例輸入
6
1 3 5 2 7 1
樣例輸出
9
說明
保證對于所有數據有，1≤n≤105,1≤a[i]≤1051≤n≤105,1≤a[i]≤105?。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int a[N], b[N];
int n;
int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];for(int i=1;i<=n;i++)b[i] = a[i] - a[i - 1];ll ans = b[1] - 1; //差分數組第一個元素特殊處理哦for(int i = 2; i <= n; i++){if(b[i] > 0)ans = ans + b[i];}cout << ans;
}
)
)
