#4739. 分发糖果(第15届-202308)
分发糖果(第15届-202308)
Background
分发糖果
题目描述:
n个学生站成一排,已知每名学生的考试成绩,老师要根据成绩按以下规则分发糖果:1、每个学生至少得到一个糖果;
2、相邻两个学生中成绩高的会获得更多的糖果;
3、相邻两个学生成绩即使相同,获得的糖果数量也可以不同。
请计算出老师最少需要准备多少颗糖果?
例如:有3个学生,他们的考试成绩分别是70,50,80,可以给第一个学生2颗糖果,给第二个学生1颗糖果,给第三个学生2颗糖果,所以最少需要准备5颗糖果。
输入描述:
共两行
第一行输入一个正整数n(1≤n≤20000),表示学生人数 第二行输入n个整数(0≤整数≤100),表示每个学生的考试成绩,整数之间以一个空格隔开输出描述:
输出一个整数,表示最少需要准备的糖果数量
样例输入:
3
70 50 80
样例输出:
5
Limitation
1s, 1024KiB for each test case.