洛谷P1091 合唱队形

旧城等待， 2022-05-28 12:16 99阅读 0赞

## 题目描述 ##

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

## 输入输出格式 ##

输入格式：

输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出格式：

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

## 输入输出样例 ##

输入样例\#1： 复制

8
    186 186 150 200 160 130 197 220

输出样例\#1： 复制

## 说明 ##

对于50％的数据，保证有n<=20；

对于全部的数据，保证有n<=100。

思路:

队列要求为中间高两头低，且不一定连续，所以联想到最长上升子序列。不同的是本题需要枚举断点来求左边和右边的最长上升子序列。

枚举中间的断点Ti,从1~Ti（左边）求一次最长上升子序列,从n~Ti+1（右边）求一次最长上升子序列（也可以从Ti+1~n求最长下降子序列）。两边的最长上升子序列的长度相加就是合唱队剩下的人数ans。用n-ans就得到踢出去多少人。

求最长上升(下降)子序列可以用队列+二分的方法

细节请看代码（有详细注释）

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    
    int n;
    int students[102];
    int left_queue[102];
    int right_queue[102];
    int ans;
    int num_left;
    int num_right;
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		cin >> students[i];
    
    	for (int i = 1; i <= n; i++)//枚举断点
    	{
    		int Ti = i;//断点
    		memset(left_queue,0,sizeof(left_queue));
    		memset(right_queue, 0, sizeof(right_queue));
    		num_left = num_right = 0;
    
    		//从左边到Ti的最长升序子序列
    		if (Ti != 1)
    		{
    			for (int j = 1; j <= Ti;j++)
    			if (students[j] > left_queue[num_left]){ left_queue[++num_left] = students[j]; }
    			else
    			{
    				int l = 1, r = num_left;
    				while (l < r)//用二分的方法求出来最长升序子序列
    				{
    					int mid = (l + r) / 2;
    					if (students[j] > left_queue[mid]) l = mid + 1;
    					else r = mid;
    				}
    				left_queue[l] = students[j];
    			}
    		}
    
    
    		//从右边到Ti的最长升序子序列
    		if (Ti != n)
    		{
    			if (Ti != 1) Ti++;//如果Ti不是1说明Ti是中间的一个值，之前已经1~Ti了，接下来处理Ti+1~n
    			for (int j = n; j >= Ti; j--)
    			{
    				if (students[j] > right_queue[num_right]){ right_queue[++num_right] = students[j]; }
    				else
    				{
    					int l = 1, r = num_right;
    					while (l < r)
    					{
    						int mid = (l + r) / 2;
    						if (students[j] > right_queue[mid]) l = mid + 1;
    						else r = mid;
    					}
    					right_queue[l] = students[j];
    				}
    			}
    		}
    		ans = max(ans, num_left + num_right);//留下来的人数
    
    	}
    	cout << n - ans;//减去留下来的人就是答案
    	return 0;
    }