蓝桥杯 小蓝的操作（一维差分）

问题描述

一个数组 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;
}