每日一题C++版（合唱队）
编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）
特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。
合唱队
题目描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述:
整数N
输出描述:
最少需要几位同学出列
示例
输入
8
186 186 150 200160 130 197 200
输出
4
分析
首先计算每个数在最大递增子串中的位置（如何计算后文有讲解）
186 186 150 200 160 130 197 200 quene
1 1 1 2 2 1 3 4 递增计数
然后计算每个数在反向最大递减子串中的位置--->计算反向后每个数在最大递增子串中的位置
200 197 130 160 200 150 186 186 反向quene
1 1 1 2 3 2 3 3 递减计数
然后将每个数的递增计数和递减计数相加
186 186 150 200 160 130 197 200 quene
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（自己在递增和递减中被重复计算）
如160这个数
在递增队列中有2个人数
150 160
在递减队列中有2个人数
160 130
那么160所在队列中就有3个人
150 160 130
每个数的所在队列人数表达就是这个意思
总人数 - 该数所在队列人数 = 需要出队的人数
所以本题关键的问题就是如何找出最大的递增序列和递减序列。递减序列可以看作倒叙后的最大递增序列。因此，关键问题就是如何找到最大递增序列。小白采用的方法是首先将每一个数都遍历一次，首先将每个数都记为单独的递增序列，也就是位数为1，之后循环的过程中进行比较，如果后一个数比自己大，则比较后一个数的位数与当前位数+1的大小，如果当前数的位数+1大于后一个数的位数，则将后一个数的位数改为当前数的位数+1，否则不变。如果后面的数比当前数小，则用后一位数与第一层循环的数进行比较，采用同样的方式对位数进行更改。之后以后一位数变成当前数，再次进行比较，直到第一层遍历结束。
代码
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
class Solution
{
public:
Solution(){}
vector<int> GetOrder(vector<int> number, int n)
{
vector<int> order(n, 1);
for (int i = 0; i < n; i++)
{
int m = number[i];
int k = i;
for (int j = i + 1; j < n; j++)
{
if (m < number[j] && order[k] >= order[j])
{
order[j] = order[k] + 1;
m = number[j];
k = j;
}
if (number[i]<number[j] && order[i] >= order[j])
{
order[j] = order[i] + 1;
m = number[j];
k = j;
}
}
}
return order;
}
int Maxorder(vector<int>Inorder, vector<int> Deorder)
{
int max;
vector<int> sum;
for (int i = 0; i < Inorder.size(); i++)
{
sum.push_back(Inorder[i] + Deorder[Inorder.size() - 1 - i]);
}
max = sum[0];
for (int i = 1; i < Inorder.size(); i++)
{
if (max < sum[i])
{
max = sum[i];
}
}
return max;
}
private:
};
int main()
{
int n;
while(cin >> n)
{
vector<int> number;
vector<int> denumber(n,0);
Solution solution;
vector<int> Inorder;
vector<int> Deorder;
for (int k = 0; k < n; k++)
{
int i;
cin >> i;
number.push_back(i);
}
for (int i = 0; i < n; i++)
{
denumber[i] = number[n-1-i];
}
Inorder = solution.GetOrder(number, n);
Deorder = solution.GetOrder(denumber, n);
int max = solution.Maxorder(Inorder, Deorder);
cout << n - max + 1 << endl;
}
return 0;
}
运行结果
