题目

描写叙述:

计算最少出列多少位同学。使得剩下的同学排成合唱队形说明：N位同学站成一排，音乐老师要请当中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这种一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1 < T2 <...... < Ti-1 < Ti >Ti+1 >......>TK。 你的任务是。已知全部N位同学的身高。计算最少须要几位同学出列，能够使得剩下的同学排成合唱队形。

题目类别:

循环

难度:

0基础

执行时间限制:

无限制

内存限制:

无限制

阶段:

入职前练习

输入:

整数N一行整数，空格隔开，N位同学身高

输出:

最少须要几位同学出列

例子输入:

8186 186 150 200 160 130 197 200

例子输出:

4

代码

/*---------------------------------------*   日期：2015-07-02*   作者：SJF0115*   题目：合唱队*   来源：华为机试练习题-----------------------------------------*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int Chorus(vector
           
             height){ int n = height.size(); if(n == 0){ return 0; }//if // left to right left[i] 统计出左边小于height[i]的身高个数（left[i] 包含height[i]本身） vector
            
              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; }//if }//if }//for }//for // right to left right[i] 统计出右边小于height[i]的身高个数（right[i] 包含height[i]本身） vector
             
               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; }//if }//if }//for }//for int max = 0; for(int i = 0;i < n;++i){ if(max < left[i] + right[i] - 1){ max = left[i] + right[i] - 1; }//if }//for return n - max;}int main(){ int n; //freopen("C:\\Users\\Administrator\\Desktop\\c++.txt","r",stdin); while(cin>>n){ vector
              
                height; int h; // 输入身高 for(int i = 0;i < n;++i){ cin>>h; height.push_back(h); }//for cout<
               
                <
               
              
             
            
           
          
         
        
       
      

#include 
      
       #include 
       
        using namespace std;int solve(int n);int main(){    int n;    //freopen("C:\\Users\\Administrator\\Desktop\\c++.txt","r",stdin);    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
        
          height;    for(int i=0;i
         
          > h;        height.push_back(h);    }    vector
          
            left(n,1), right(n,1);    for(int i=0;i
           
            height[j]) if(left[i]
            
             < n;++k){ if(height[n-i-1]>height[k]) if(right[n-i-1]
             
              < n;++i){ cout<
              
               <<" "; } cout<
               
                < n;++i){ cout<
                
                 <<" "; } cout<