[编程题]合唱队

ゝ一世哀愁。 2022-07-14 14:45 125阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

计算最少出列多少位同学，使得剩下的同学排成合唱队形  
说明：  
  
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。  
  
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1

### 二、问题分析 ###

按照题意，不能打乱原来同学的排列次序，只能从中出列一些同学。要求解整个问题，可以考虑递归的思路来解决，递归的结束条件是当现有序列已经构成合唱队队形，如果还没有达到要求，就考虑依次出列一个序列元素，比如8个元素的序列是，依次出列每个元素，然后剩下的7个元素的排列就是递归的子问题，一共需要计算8次，求出这8次中需要出列的元素最大值就是问题的解。这是一种思路，但是解决问题的复杂度较高，为阶乘复杂度。  
另外一种比较推荐的方式是把每个元素当做拍好队形中的身高最高的人来考虑，8个元素第一次也是考虑8个子问题。计算这8个子问题时需要知道当前身高最高的人的前面的最长递增子序列长度，和当前身高最高的人后面的最长递减子序列长度，这样就可以计算出这个人作为身高最高的人排好队形后的人数，再用总人数减去排好队形的人数，就是这个人作为身高最高的人排列队形时需要出列的人数。现在，问题就转化成为计算某个人的最长递增子序列长度的问题了，最长递增子序列长度计算可以采用动态规划的方法，先计算第一个人的最长递增子序列长度，在计算前两个人的最长递增子序列长度，依次往后。

**解题方式1：**

按照求最长递增子序列的方式来解决：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    // 基本思路，两遍最长递增子序列，并找和最大
    int main(void)
    {
        int n;
        while (cin >> n)
        {
            int tmp;
            vector<int> queue;
            vector<int> dp_1(n, 1);
            vector<int> dp_2(n, 1);
    
            for (int i = 0; i < n; ++i)
            {
                cin >> tmp;
                queue.push_back(tmp);
            }
    
            // 第一遍dp
            for (int i = 0; i < n; ++i)
            {
                for (int j = i - 1; j >= 0; --j)
                {
                    if (queue[i] > queue[j] && dp_1[i] < dp_1[j] + 1)
                        dp_1[i] = dp_1[j] + 1;
                }
            }
    
            std::reverse(queue.begin(), queue.end());
            // 第二遍dp
            for (int i = 0; i < n; ++i)
            {
                for (int j = i - 1; j >= 0; --j)
                {
                    if (queue[i] > queue[j] && dp_2[i] < dp_2[j] + 1)
                        dp_2[i] = dp_2[j] + 1;
                }
            }
            std::reverse(dp_2.begin(), dp_2.end());
    
            int max = -1;
            int sum;
            for (int i = 0; i < n; ++i)
            {
                sum = dp_1[i] + dp_2[i];
                if (sum > max)
                {
                    max = sum;
                }
            }
            cout << n - max + 1 << endl;
        }
        return 0;
    }

**解题方式2：**

按照递归的思路来做，复杂度过高，没有通过OJ的时间限制，但是方案是可行的，结果也是正确的。

#include <iostream>
    #include <vector>
    #include <iterator>
    using namespace std;
    
    int decreaseSort(vector<int> vect)
    {
        int i = 1, maxIndex = 0, max = 0;
        while (i < vect.size())
        {
            if (vect[i] >= vect[i - 1])
            {
                if (vect[i] >= max)
                {
                    max = vect[i];
                    maxIndex = i;
                }
            }
            i++;
        }
        int del = 0;
    //递归终止条件
        if (maxIndex == 0)
        {
            return del;
        } else {
    //去掉最大凸起的前面部分
            vector<int> front;
            for (int i = 0; i < maxIndex; i++)
            {
                if (vect[i] > max)
                {
                    front.push_back(vect[i]);
                } else {
                    del++;
                }
            }
            for (int i = maxIndex; i < vect.size(); i++)
            {
                front.push_back(vect[i]);
            }
            del += decreaseSort(front);
            int mindel = del;
    //去掉最大凸起的后面部分
            vector<int> back;
            del = 0;
            for (int i = 0; i < maxIndex; i++)
            {
                back.push_back(vect[i]);
            }
            for (int i = maxIndex; i < vect.size(); i++)
            {
                if (vect[i] >= vect[maxIndex - 1])
                {
                    del++;
                } else {
                    back.push_back(vect[i]);
                }
            }
            del += decreaseSort(back);
            if (del < mindel)
            {
                mindel = del;
            }
            return mindel;
        }
    }
    
    int increaseSort(vector<int> vect)
    {
        int i = 1, maxIndex = -1, max = 0;
        while (i < vect.size())
        {
            if (vect[i] <= vect[i - 1])
            {
                if (vect[i - 1] >= max)
                {
                    max = vect[i - 1];
                    maxIndex = i - 1;
                }
            }
            i++;
        }
        int del = 0;
    //递归终止条件
        if (maxIndex == -1)
        {
            return 0;
        } else {
    //删除最大凸起前半部分
            vector<int> front;
            for (int i = 0; i <= maxIndex; i++)
            {
                if (vect[i] < vect[maxIndex + 1])
                {
                    front.push_back(vect[i]);
                } else {
                    del++;
                }
            }
            for (int i = maxIndex + 1; i < vect.size(); i++)
            {
                front.push_back(vect[i]);
            }
            del += increaseSort(front);
            int mindel = del;
    //去掉最大凸起的后面部分
            vector<int> back;
            del = 0;
            for (int i = 0; i <= maxIndex; i++)
            {
                back.push_back(vect[i]);
            }
            for (int i = maxIndex + 1; i < vect.size(); i++)
            {
                if (vect[i] <= vect[maxIndex])
                {
                    del++;
                } else {
                    back.push_back(vect[i]);
                }
            }
            del += increaseSort(back);
            if (del < mindel)
            {
                mindel = del;
            }
            return mindel;
        }
    }
    
    int main()
    {
        int num, temp;
        while (cin >> num)
        {
        vector<int> vect;
        while (num--)
        {
            cin >> temp;
            vect.push_back(temp);
        }
        int mindel = vect.size();
        for (int i = 0; i < vect.size(); i++)
        {
            vector<int> front, back;
            for (int j = 0; j <= i; j++)
            {
                front.push_back(vect[j]);
            }
            for (int j = i; j < vect.size(); j++)
            {
                back.push_back(vect[j]);
            }
            int idel = increaseSort(front);
            int ddel = decreaseSort(back);
            int del = idel + ddel;
            if (del < mindel)
            {
                mindel = del;
            }
        }
        cout << mindel << endl;
        }
        return 0;
    }