AC记录：ACAC

题目描述

给定一个长度为 n的序列，你可以将某些各减去一个数，使得整个序列严格递增。

你需要求出所有减去的数的总和的最小值。

例如：有一个长度为 3的序列 5,5,5；最优方案是 5-2,5-1,5即3,4,5。这样所有减去的数的总和是 2+1=3，为最小值。

输入格式

输入第一行一个整数 n，表示序列的长度。

第二行 n 个整数，描述这个序列。

输出格式

输出一行一个整数，表示总和的最小值。

输入输出样例

输入 #1复制

3
5
5
5

输出 #1复制

3

输入 #2复制

4
5
3
7
5

输出 #2复制

6

说明/提示

数据规模与约定

对于 100% 的数据，保证1≤n≤100，序列中的数字皆为不大于20000 的正整数。

说明

题目译自 COCI2010-2011 CONTEST #6 T3 RAZINE。

CODE

#include <cstdio>
#include <iostream>
#define N 101
using namespace std;

int n, a[N];
typedef long long ll;
ll ans;

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);
	for(int i=n-1; i>=1; i--)
		if(a[i] >= a[i+1]){
			ans += (a[i] - a[i+1] + 1);
			a[i] = a[i+1] - 1;
		}
	cout << ans << endl;
	return 0;
}