算法题-合唱队

合唱队

https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4?tpId=37&tqId=21247&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking

题目描述

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

说明：

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

输出描述:

最少需要几位同学出列

示例1

输入

复制

8
186 186 150 200 160 130 197 200

输出

复制

题解

如果需要使出列的人数最少，则应该选择串中元素所能组成的最长的子串并符合规则左边的k1 < k2 < ... < kx > kx+1 > kx+2 > ... > kn

所以需要求出每个元素的所有左边最长符合条件的子串以及右边最长符合条件的子串

求取某一边最长子串是对该边每一个元素进行计算，求取该元素该边的最长子串，所以可得公式

最长符合条件的子串为

符合条件的 k_n > k_n-1, k_n = max(k_n-1,k_n-2,...,k₀) + 1

转化成一个求取最大递增子串的问题

看题目例子：

首先计算每个元素最大递增子串

186
186 150 200 160 130 197 200

1 1 1 2 2 1 3 4

反向计算每个元素最大递增子串

200 197 130 160 200 150 186 186

1 1 1 2 3 2 3 3

然后将每个元素的递增子串相加求最大和

186 186 150 200 160 130 197 200

1 1 1 2 2 1 3 4

3 3 2 3 2 1 1 1

4
4 3 5 4 2 4 5

同一个元素在累加正向和反向数值是被加了两次，所以此处最终要-1，例如第四个元素200的正向递增子串是150 200，反向递增子串是130 160 200，本身被多累加一次

所以最终的出列人数是8-5+1=4

代码如下：
#include <bits/stdc++.h> using namespace std; void getMaxSubLength(const std::vector<int> & vHigh, std::vector<int> &vMaxSubLength) { for(int iLocation = 1; iLocation < vHigh.size(); ++iLocation) { for(int iLocationLast = iLocation - 1; iLocationLast >= 0; --iLocationLast) { if(vHigh.at(iLocationLast) < vHigh.at(iLocation) && vMaxSubLength[iLocation] < vMaxSubLength[iLocationLast] + 1) { vMaxSubLength[iLocation] = vMaxSubLength.at(iLocationLast) + 1; } } } } int main() { //freopen("test.in", "r+", stdin); //freopen("test.out", "w+", stdout); int iNum; while(cin >> iNum) { std::vector<int> vHigh; std::vector<int> vMaxSubLength(iNum, 1); std::vector<int> vMaxRevSubLength(iNum, 1); std::vector<int> vMaxLength; vHigh.clear(); while(iNum--) { int iInput; std::cin >> iInput; vHigh.push_back(iInput); } getMaxSubLength(vHigh, vMaxSubLength); std::reverse(vHigh.begin(), vHigh.end()); getMaxSubLength(vHigh, vMaxRevSubLength); std::reverse(vMaxRevSubLength.begin(), vMaxRevSubLength.end()); for(int iLocation = 0; iLocation < vMaxSubLength.size(); ++iLocation) { vMaxLength.push_back(vMaxSubLength.at(iLocation) + vMaxRevSubLength.at(iLocation)); } std::cout << vHigh.size() - *std::max_element(vMaxLength.begin(), vMaxLength.end()) + 1 << std::endl; } return 0; }