牛客-减成一
看到这道题的AC代码真的再一次感叹:算法的精妙啊~
题目链接: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
题意很好理解,对区间里的数同时减1,直至所有数变成1
9次操作分别为:
- 1 2 4 1 7 1
- 1 1 3 1 7 1
- 1 1 2 1 7 1
- 1 1 1 1 6 1
- 1 1 1 1 5 1
- 1 1 1 1 4 1
- 1 1 1 1 3 1
- 1 1 1 1 2 1
- 1 1 1 1 1 1
对于一段都大于1的区间,很容易想到,次数就取决于最大的那个数 如352
,但要解出此题还需要更开阔的思维
算法思路
对于区间a[1:n]初始化a[0]=1;
减1的操作可以用a[i+1]-a[i]
来替代,当然前提是a[i]<a[i+1]
;
然后累加就得到结果了……
————————————————代码如下————————————————————
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!