HJ24 合唱队 题解

by 限时烟花

1. 抽丝剥茧

抽象题目的核心问题：在一个无序数列中找到最长的先增后减（包括单调递增或单点递减）的子序列

2. 化繁为简

“最长先增后减的子序列”没听说过，但是一定听说过“最长递增子序列”。那么从同样的角度进行思考，可以考虑使用DP， 即可以将题目拆解为：

1. 使用正序遍历“身高数组”，得到第一个$dp\_h\left[\right]dp\backslash \_h[\backslash \; \backslash \; ]$dp_h[  ]数组。其中$dp\_h\left[i\right]dp\backslash \_h[\backslash \; i\backslash \; ]$dp_h[ i ]表示从第$00$0位到第$ii$i位，这之中以第$ii$i位结尾的最长递增子序列包含的元素的个数。对于$dp\_h\left[i\right]dp\backslash \_h[\backslash \; i\backslash \; ]$dp_h[ i ]，是从$dp\_hdp\backslash \_h$dp_h数组中在它之前的所有元素中，找到小于对应“身高值”的最大dp值最大的那个，因此我们有：

2. 使用逆序遍历“身高数组”，得到第二个$dp\_t\left[\right]dp\backslash \_t[\backslash \; \backslash \; ]$dp_t[  ]数组。其中$dp\_t\left[i\right]dp\backslash \_t[\backslash \; i\backslash \; ]$dp_t[ i ]表示从第$n-1n-1$n−1位到第$ii$i位，这之中以第$ii$i位开头的最长递减子序列包含的元素的个数。对于$dp\_t\left[i\right]dp\backslash \_t[\backslash \; i\backslash \; ]$dp_t[ i ]，是从$dp\_tdp\backslash \_t$dp_t数组中在它之后的所有元素中，找到小于对应“身高值”的dp值最大的那个，因此我们有

3. 对两个dp数组中的值进行按序加和减去一，并求最大值，代表一个子序列先递增后递减并且具有的最大的长度；
4. 用$nn$n减去这个最大长度获得最少的需要出列的人数。

3. 码上行动

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, tmp;
    int i, j;
    vector<int> heights;
    // 输入
    while(cin >> n){
        for(i = 0; i < n; i++){
            cin >> tmp;
            heights.push_back(tmp);
        }
        // 设置两个dp数组
        vector<int> dp_h(n, 1), dp_t(n, 1);
        // 正序遍历
        for(i = 0; i < n; i++){
            for(j = 0; j < i; j++){
                if(heights[i] > heights[j]){
                    dp_h[i] = max(dp_h[i], dp_h[j] + 1);
                }
            }
        }
        // 逆序遍历
        for(i = n-1; i >= 0; i--){
            for(j = n-1; j > i; j--){
                if(heights[i] > heights[j]){
                    dp_t[i] = max(dp_t[i], dp_t[j] + 1);
                }
            }
        }
        // 求和得到最长先增后减子序列的长度
        int maxNum = 0;
        for(i = 0; i < n; i++){
            if(dp_t[i] + dp_h[i] - 1 > maxNum)
                maxNum = dp_t[i] + dp_h[i] - 1;
        }
        // 输出
        cout << n - maxNum << endl;
        // 清除vector，以供下一轮使用
        heights.clear();
    }
    return 0;
}

4. 心有成算

1. 时间复杂度：由于用到了两层循环，故时间复杂度为$O\left(n^2\right)O(n^2)$O(n2)
2. 空间复杂度：使用两个dp数组辅助记录，故空间复杂度为$O\left(n\right)O(n)$O(n)

5. 左右逢源

解法一分析：

解法一中内层循环的作用其实是在一个“范围”内（从左往右到自己/从右往左到自己）找到比自身元素的所有元素对应的dp值的最大值。 但是由于程序没有“记忆”，所以对于每一次的循环都需要对所有的“范围”内的元素做一次遍历。因此我们考虑是否能设定一个cache数组，来存储一些当前已经遍历过的数组中的一些“比较小”的值。

cache数组的形成和更新

cache数组目标工作有两点：

1. 尽可能的生成长的子序列；
2. 尽可能保持其中的元素足够小，来为第1点提供足够大的空间。

要做到这两点，我们可以设想一个这样的cache数组满足：

1. 数组中的下标与子序列长度建立对应关系，即：$Index=length-1Index\; =\; length\; -\; 1$Index=length−1；
2. 对于$cache\left[i\right]cache[\backslash \; i\backslash \; ]$cache[ i ]，其中保留的值是所有长度为$i+1i+1$i+1的子序列中，结尾元素的最小值。

所以有以下的工作流程：

1. 如果cache数组中没有找到比当前值更大的元素，那么证明这给元素足够大，探索到了我们之前没有探索到的长度，能够形成更长的子序列，所以我们需要将这个元素加入cache中；
2. 如果能够在$ii$i的位置找到$cache\left[i\right]cache[\backslash \; i\backslash \; ]$cache[ i ]比当前值大，则证明可以形成一个结尾元素更小的长度为$i+1i+1$i+1的子序列，所以需要用当前值对$cache\left[i\right]cache[\backslash \; i\backslash \; ]$cache[ i ]进行更新。

优化解法：辅助数组 + 二分法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, tmp;
    int i, j;
    vector<int> heights;
    // 输入
    while(cin >> n){
        for(i = 0; i < n; i++){
            cin >> tmp;
            heights.push_back(tmp);
        }
        // 设置两个dp数组
        vector<int> dp_h(n), dp_t(n);
        // 设置cache数组
        vector<int> cache;

        // 正序遍历
        for(i = 0; i < n; i++){
        	// 在当前cache中找到最小的大于等于当前值的元素的下标
        	// 其中，lower_bound()函数是定义在algorithm头文件中的二分查找函数
            int potIndex = lower_bound(cache.begin(), cache.end(), heights[i]) - cache.begin();
            dp_h[i] = potIndex + 1;
            /*
            lower_bound()函数如果找不到比当前值小的元素时，返回end()迭代器
            此时potIndex变量的值将大于cache的大小。
            即此处表示能在cache中找到大于等于当前值的元素
            对其进行更新，用当前值（<= cache[potIndex]）替换cache[potIndex]
            由于我们只需要找到一个最长的子序列就可以，所以我们要保证cache中的元素尽量小
            较小的元素能够在效果上代表更大的值
			*/
            if(potIndex < cache.size())
            	cache[potIndex] = heights[i];
            else
            	cache.push_back(heights[i]);

        }
        cache.clear();
        // 逆序遍历
        for(i = n-1; i >= 0; i--){
            int potIndex = lower_bound(cache.begin(), cache.end(), heights[i]) - cache.begin();
            dp_t[i] = potIndex + 1;
            if(potIndex < cache.size())
            	cache[potIndex] = heights[i];
            else
            	cache.push_back(heights[i]);
        }
        // 求和得到最长先增后减子序列的长度
        int maxNum = 0;
        for(i = 0; i < n; i++){
            if(dp_t[i] + dp_h[i] - 1 > maxNum)
                maxNum = dp_t[i] + dp_h[i] - 1;
        }
        // 输出
        cout << n - maxNum << endl;
        // 清除vector，以供下一轮使用
        heights.clear();
    }
    return 0;
}

♥️ 可用下图增加理解 ♥️

复杂度：

1. 时间复杂度：在循环内部使用二分法，故时间复杂度为$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n) ；
2. 空间复杂度：使用三个辅助vector，故空间复杂度为$O\left(n\right)O(n)$O(n)。