题目
描述:
计算最少出列多少位同学,使得剩下的同学排成合唱队形
说明:
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足存在i(1<=i<=K)使得T1 < T2 <...... < Ti-1 < Ti >Ti+1 >......>TK。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
题目类别:
循环
难度:
初级
运行时间限制:
无限制
内存限制:
无限制
阶段:
入职前练习
输入:
整数N
一行整数,空格隔开,N位同学身高
输出:
最少需要几位同学出列
样例输入:
8
186 186 150 200 160 130 197 200
样例输出:
4
代码
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
using namespace std;
int Chorus(vector<int> height){
int n = height.size();
if(n == 0){
return 0;
}
vector<int> left(n,1);
for(int i = 1;i < n;++i){
for(int j = i-1;j >=0;--j){
if(height[i] > height[j]){
if(left[i] < left[j]+1){
left[i] = left[j]+1;
}
}
}
}
vector<int> right(n,1);
for(int i = n-2;i >= 0;--i){
for(int j = i+1;j < n;++j){
if(height[i] > height[j]){
if(right[i] < right[j]+1){
right[i] = right[j]+1;
}
}
}
}
int max = 0;
for(int i = 0;i < n;++i){
if(max < left[i] + right[i] - 1){
max = left[i] + right[i] - 1;
}
}
return n - max;
}
int main(){
int n;
while(cin>>n){
vector<int> height;
int h;
for(int i = 0;i < n;++i){
cin>>h;
height.push_back(h);
}
cout<<Chorus(height)<<endl;
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int solve(int n);
int main(){
int n;
while(cin>>n){
cout << solve(n) << endl;
}
return 0;
}
int solve(int n){
if(n==0 || n==1)
return 0;
int res = 0,h=0;
vector<int> height;
for(int i=0;i<n;i++){
cin >> h;
height.push_back(h);
}
vector<int> left(n,1), right(n,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(height[i]>height[j])
if(left[i]<left[j]+1)
left[i] = left[j]+1;
}
for(int k = n-i;k < n;++k){
if(height[n-i-1]>height[k])
if(right[n-i-1]<right[k]+1)
right[n-i-1]=right[k]+1;
}
}
res = left[0] + right[0] -1;
for(int j=1;j<n;j++)
if(res<left[j] + right[j] -1)
res = left[j] + right[j] -1;
return n-res;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
华为机试一霸教你过华为机试演讲稿..pdf
华为OD机试(..75.rar
华为机试真题(非牛客网试练题)OD考试真题,不定期更新,文档含代码解答
华为机试一霸教你过华为机试.doc
华为机试一霸教你过华为机试。大菊厂招聘有三关,心理测试,机试,面试。
。。。
。。。
华为机试算法题总结 经验分享
华为机试oj练习题2014
华为机试一霸教你过华为机试e-18页.pdf
华为OD系列--华为OD机试
本人在准备2014年华为机试的时候,进行整理的,代码全部运行成功。如有错误,请大家见谅。
华为机试题目100题练习题
华为机试成功归来,与小伙伴们分享下经验
大师兄教你如何过华为机试
贰壹贰叁零华为OD机试.pptx 华为OD机试.pptx 华为OD机试.pptx
华为机试.md
里面有几十道华为历届考过的机试题,可供大家研究和参考,主要是里面的思想,只要理解透了里面的思想,非常有助于机试。
华为机试.py
2014重邮华为机试(2013.9.14和2013.9.15)一共三场的题目