徐老师的班级座位
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
众所周知，徐老师热衷于给班级的同学们排座位，希望以此来促进同学们的学习这天徐老师又有了一个新的座位思路——让成绩好的同学和成绩差的同学交叉着坐
是不是就可以让成绩差的同学更好的向成绩好的同学学习，让成绩好的同学更好的帮助成绩差的同学呢？
现在徐老师已经把前 $n$ 位同学的座位排好了，但是他发现好像座位排的有点问题
于是徐老师决定重新设定要求，他认为只要对于第 $i$ 位同学来说，要么他左右两侧的同学成绩都比他好，要么左右两侧的同学成绩都比他差，那么就满足徐老师的要求
当然，这里头尾两位同学不需要满足上述条件
现在徐老师想知道，如果他有足够多任意成绩的同学，最少需要替换这 $n$ 个同学中的几个人，可以使得这个座位满足徐老师的要求？
输入格式
输入第一行包含一个整数 $n$ 表示现在的人数输入第二行包含 $n$ 个整数 $a_i$，分别表示每个同学的成绩
|测试数据|$n$|特殊性质|
|:---:|:---:|:---:|
|$1$|$1 \leq n \leq 20$|无|
|$2 \sim 3$|$1 \leq n \leq 1000$|无|
|$4$|$1 \leq n \leq 10^5$|$a_i$均不相同|
|$5$|$1 \leq n \leq 10^5$|$a_i==1$|
|$6 \sim 10$|$1 \leq n \leq 10^5$|无|
对于所有数据满足：$1 \leq a_i \leq 10^9$
|:---:|:---:|:---:|
|$1$|$1 \leq n \leq 20$|无|
|$2 \sim 3$|$1 \leq n \leq 1000$|无|
|$4$|$1 \leq n \leq 10^5$|$a_i$均不相同|
|$5$|$1 \leq n \leq 10^5$|$a_i==1$|
|$6 \sim 10$|$1 \leq n \leq 10^5$|无|
对于所有数据满足：$1 \leq a_i \leq 10^9$
输出格式
输出最少需要替换几个同学样例
6
1 1 2 2 3 33提示
其中一组方案为：替换 $1$ 号同学为一位成绩为 $2$ 的同学
替换 $4$ 号同学为一位成绩为 $1$ 的同学
替换 $6$ 号同学为一位成绩为 $1$ 的同学
最后 $6$ 位同学的成绩分别为 $2,1,2,1,3,1$ 满足徐老师的要求
23CSP-J秋季普及组模拟赛(4)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-9-30 12:00
- 结束于
- 2023-10-10 12:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 55
