网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
合唱团
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 09:25 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 09:25 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 09:25 |
输入文件 | chorus.in | 输出文件 | chorus.out |
【题目描述】合唱团(chorus.cpp/c/pas)NOIP 2004
N位同学站成一排,墨老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<T2<…<Ti>Ti+1>…>TK(1≤i≤K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
【输入文件】
输入文件chorus.in的第一行是一个整数N(2≤N≤100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130≤Ti≤230)是第i位同学的身高(厘米)。
【输出文件】
输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
【输入样例】
8
186 186 150 200 160 130 197 220
【输出样例】
4
【数据规模】
对于50%的数据,保证有n≤20;
对于全部的数据,保证有n≤100。