[蓝桥杯国赛 2022 中级组] 分铅笔

[蓝桥杯国赛 2022 中级组] 分铅笔

时间限制:\(3000\) MS

内存限制:\(589824\) KB

【题目描述】

老师要奖励 \(N\) 名成绩优秀的同学,首先 \(N\) 名同学按随机顺序排成一排,且每名同学都对应一个成绩(成绩各不相同),然后按照如下规则进行奖励。

规则:

  1. 每名同学至少奖励 \(1\) 支铅笔;

  2. 每一名同学拿到铅笔后,都会和左右相邻的同学作比较,如果相邻的同学成绩比自己高,那么铅笔数也一定比自己多,如果相邻的同学成绩比自己低,那么铅笔数一定比自己少。(注意每个人成绩都不同)

当给出要奖励的同学数 \(N\),及 \(N\) 名同学的成绩及排序位置,请你按照规则帮助老师计算出最少需要奖励多少支铅笔。

【输入格式】

第一行输入一个正整数 \(N\),\(N\) 表示要奖励的同学数。

第二行输入 \(N\) 个正整数,每个正整数表示一名同学的成绩(成绩各不相同),正整数之间以一个英文逗号隔开,正整数的顺序即代表学生的顺序。

【输出格式】

输出一个整数,表示 \(N\) 名同学最少需要奖励的铅笔数。

样例 1

【样例 1 输入】

3
91,94,92

【样例 1 输出】

4

【样例 1 解释】

成绩为 \(91\) 的同学 \(1\) 支,成绩为 \(94\) 的同学 \(2\) 支,成绩为 \(92\) 的同学 \(1\) 支。

样例 2

【样例 2 输入】

3
91,92,94

【样例 2 输出】

6

【样例 2 解释】

成绩为 \(91\) 的同学 \(1\) 支,成绩为 \(92\) 的同学 \(2\) 支,成绩为 \(94\) 的同学 \(3\) 支。

信息

ID
1062
难度
2
分类
(无)
标签
递交数
62
已通过
2
通过率
3%
上传者