算法题-合唱队
合唱队
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
输出描述:
最少需要几位同学出列
题解
如果需要使出列的人数最少，则应该选择串中元素所能组成的最长的子串并符合规则左边的k1 < k2 < ... < kx > kx+1 > kx+2 > ... > kn
所以需要求出每个元素的所有左边最长符合条件的子串以及右边最长符合条件的子串
求取某一边最长子串是对该边每一个元素进行计算，求取该元素该边的最长子串，所以可得公式
最长符合条件的子串为
符合条件的 kn > kn-1, kn = max(kn-1,kn-2,...,k0) + 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 |
所以最终的出列人数是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;
}
蔚来公司氛围 182人发布
