[华为机试练习题]37.合唱队

题目

描述:

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

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

代码

/*---------------------------------------
*   日期：2015-07-02
*   作者：SJF0115
*   题目：合唱队
*   来源：华为机试练习题
-----------------------------------------*/
#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;
    }//if
    // left to right left[i] 统计出左边小于height[i]的身高个数（left[i] 包括height[i]本身）
    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;
                }//if
            }//if
        }//for
    }//for
    // right to left  right[i] 统计出右边小于height[i]的身高个数（right[i] 包括height[i]本身）
    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;
                }//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<int> height;
        int h;
        // 输入身高
        for(int i = 0;i < n;++i){
            cin>>h;
            height.push_back(h);
        }//for
        cout<<Chorus(height)<<endl;
    }//while
    return 0;
}

#include <iostream>
#include <vector>
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<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++){
        //统计i左边小于height[i]的人数
        for(int j=0;j<i;j++){
            if(height[i]>height[j])
                if(left[i]<left[j]+1)
                    left[i] = left[j]+1;
        }
        //统计i右边小于height[i]的人数
        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;
        }
    }
    /*for(int i = 0;i < n;++i){
        cout<<left[i]<<" ";
    }
    cout<<endl;
    for(int i = 0;i < n;++i){
        cout<<right[i]<<" ";
    }
    cout<<endl;*/
    //选出最小的人数
    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;
}