合唱队列问题

发布于:2021-10-18 20:25:22

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


合唱队列说明:


N位同学中,使(N-K)位出列,使得剩下的满足条件:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,???则他们的身高满足存在i(1<=i<=K)使得T1Ti+1>......>TK。


计算出最少需要出列的同学数。


?


#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

//需要关注每个同学左边满足合唱队列的数(加上自己)
//总人数 - 该数所在队列人数 + 1 = 需要出队的人数
/*
186 186 150 200 163 130 197 200 orig_num

1 1 1 2 2 1 3 4 递增计数

200 197 130 163 200 150 186 186 反向orig_num

1 1 1 2 3 2 3 3 递减计数

然后将每个数的递增计数和递减计数相加

186 186 150 200 163 130 197 200 orig_num

1 1 1 2 2 1 3 4 递增计数

3 3 2 3 2 1 1 1 递减计数

4 4 3 5 4 2 4 5 相加,计算队列长度(自己在递增和递减中被重复计算)


如163这个数

在递增队列中有2个人数
150 163

在递减队列中有2个人数
163 130

那么163所在队列中就有3个人

150 163 130

*/
void calculate_num(vector orig_num, vector &num)
{
for(int i = 1; i < orig_num.size(); ++i)
{
for(int j = i - 1; j >= 0; --j)
{
if((orig_num[i] > orig_num[j]) && (num[i] < num[j] + 1))
{
num[i] = num[j] + 1;
}
}
}
}


int main()
{
int n = 0;
int tmp = 0;


while(cin >> n)
{

vector num1(n,1);//递增
vector num2(n,1);//递减
//必须放到while中(局部变量),不然多次输入会使orig_num.size()大与n
//从而导致num1和num2越界
vector orig_num;

for(int i = 0; i< n; ++i)
{
cin >> tmp;
orig_num.push_back(tmp);
}

calculate_num(orig_num, num1);
reverse(orig_num.begin(), orig_num.end());
calculate_num(orig_num, num2);
reverse(num2.begin(), num2.end());

int max_num = 0;

for(int i = 0; i < n; ++i)
{
if(num1[i] + num2[i] > max_num)
{
max_num = num1[i] + num2[i];
}
}

cout<
}

return 0;
}

?


?

相关推荐

最新更新

猜你喜欢