2281. 分糖果
1000ms
256MB
中等
贪心算法
题目描述
Alice 老师要给排成一排的 $n$ 个孩子分发糖果。每个孩子都有一个表现评分 $arr[i]$。分发规则如下：
1. 每个孩子至少分到 1 颗糖果。
2. 相邻的两个孩子中，评分更高的孩子必须获得更多的糖果。
请计算 Alice 老师最少需要准备多少颗糖果。
输入格式
- 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示孩子的数量。
- 接下来 $n$ 行，每行包含一个整数 $arr[i]$ ($1 \le arr[i] \le 10^5$)，表示每个孩子的评分。
输出格式
输出一个整数，表示 Alice 必须购买的最少糖果总数。
样例 1
输入 (Input)
3 1 2 2
输出 (Output)
4
样例 2
输入 (Input)
10 2 4 2 6 1 7 8 9 2 1
输出 (Output)
19
样例 3
输入 (Input)
8 2 4 3 5 2 6 4 5
输出 (Output)
12
- 对于所有数据：$1 \le n \le 10^5$，$1 \le arr[i] \le 10^5$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功