算法

科林明伦杯

B 减成一

链接:https://ac.nowcoder.com/acm/contest/5758/B
来源:牛客网

题目描述

存在n个数,每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作,可以让所有数都变成1。
数据保证一定有解。

输入描述:

输入t,代表有t组数据。每组数据输入n,代表有n个数。接下来一行输入n个数,数字大小小于1e6。(t<=1000,n<1e5,∑n < 1e6)

输出描述:

每组数据输出一个整数代表最少需要操作的次数。

输入

1
6
1 3 5 2 7 1

输出

9

我的代码

#include<stdio.h>

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int array[100000]={0};
		int n,ans=0,num,pre=0;
		scanf("%d",&n);
		for (int i=0;i<n;i++)
		{
			scanf("%d",&array[i]);
			if (i==0)
			{
				ans+=array[i]-1;
			}
			else
			{
				ans+=(array[i-1]>array[i]?0:(array[i]-array[i-1]));
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

发表评论