赣州做网站公司/网站百度收录查询

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

合唱队形是指这样的一种队形：设 KK 位同学从左到右依次编号为 1，2，\cdots K1，2，⋯K，他们的身高分别为 T_1，T_2，\cdots，T_KT1​，T2​，⋯，TK​， 则他们的身高满足 T_1< \cdots < T_i> T_{i+1}> \cdots >T_K(1 \leq i \leq K)T1​<⋯<Ti​>Ti+1​>⋯>TK​(1≤i≤K)。

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

输入描述

输入两行。

第一行是一个整数 N\ (2 \leq N \leq 100)N (2≤N≤100)，表示同学的总数。

第二行有 nn 个整数，用空格分隔，第 ii 个整数 T_i(130 \leq T_i \leq 230)Ti​(130≤Ti​≤230) 是第 ii 位同学的身高(厘米)。

输出描述

输出一个整数，就是最少需要几位同学出列。

输入输出样例

示例 1

输入

8
186 186 150 200 160 130 197 220 

输出

4

解：按题目要求，我们需要找到是一个先递增再递减的序列，总人数减去这个序列中人数即为结果。我们分别设置d1,d2两个数组存放升序列和减序列（逆增序）的最大长度，再找出最大值即可。

代码：

#include <stdio.h>
#include <stdlib.h>int max(int a,int b){return a>b?a:b;
}int main(int argc, char *argv[])
{int n;int a[100]={'\0'},d1[100]={'\0'},d2[100]={'\0'};scanf("%d",&n);            //输入数据for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int j=0;j<n;j++){                   //寻找最长增序列d1[j]=1;for(int i=0;i<j;i++){if(a[j]>a[i]){d1[j]=max(d1[j],d1[i]+1);}}}for(int k=n-1;k>=0;k--){                 //寻找最长减序列d2[k]=1;for(int i=n-1;i>k;i--){if(a[k]>a[i]){d2[k]=max(d2[k],d2[i]+1);}}}int m=1;for(int p=0;p<n;p++){                   //求出满足题意的最大值if(m<(d1[p]+d2[p])){m=d1[p]+d2[p];}}printf("%d",n-m+1);       //在计算最大长度时，最大的数字被计算了两次，所有需要减1：n-(m-1)return 0;
}