首页 > 试题广场 >

合唱队

[编程题]合唱队

热度指数：294924 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

设 $K$ 位同学从左到右依次编号为 1，2…，K ，他们的身高分别为 $T_1,T_2,…,T_K$ ，若存在 $i(1\leq i\leq K)$ 使得 $T_1<T_2<......<T_{i-1}<T_i$ 且 $T_i>T_{i+1}>......>T_K$ ，则称这 $K$ 名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

例子：

123 124 125 123 121 是一个合唱队形

123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求

123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

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

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

数据范围： $1 \le n \le 3000 \$

输入描述:

用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输出描述:

最少需要几位同学出列

示例1

输入

8
186 186 150 200 160 130 197 200

输出

说明

由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130

算法知识视频讲解

牛客364244344号

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

void GetIncreaseLen(int dp_increase[], int num[], int len)
{
    dp_increase[0] = 1;
    for(int i = 1; i < len; i++){
        dp_increase[i] = 1;
        for(int j = 0; j < i; j++){
            if(num[i] > num[j]){
                int temp = dp_increase[j] + 1;
                dp_increase[i] = max(temp, dp_increase[i]);
            }
        }
    }

}

void GetDecreaseLen(int dp_decrease[], int num[], int len)
{
    dp_decrease[len-1] = 1;
    for(int i = len-2; i >= 0; i--){
        dp_decrease[i] = 1;
        for(int j = len-1; j > i; j--){
            if(num[i] > num[j]){
                int temp = dp_decrease[j] + 1;
                dp_decrease[i] = max(temp, dp_decrease[i]);
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    int num[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &num[i]);
    }
    int res = 0;
    if(n == 1){
        res = 0;
    }else if(n == 2){
        res = 1;
    }else{
        int dp_increse[n];
        int dp_decrese[n];
        int maxLen = 1;
        GetIncreaseLen(dp_increse, num, n);
        GetDecreaseLen(dp_decrese, num, n);
        for(int i = 0; i < n; i++){
            if(dp_increse[i] == 1 || dp_decrese[i] == 1){
                continue;
            }
            maxLen = max(maxLen, (dp_decrese[i]+dp_increse[i]-1));
        }
        res = n - maxLen;
    }
    printf("%d\n", res);
    return 0;
}

发表于 2023-11-15 22:19:05 回复(0)

帅气的大魔王喜欢摸鱼

#include <stdio.h>
#include <stdlib.h>

void search(int* hight, int* top, int* len) {
    static int sta[1500] = {};
    for (int x = *top; x >= 0; x--)
        if (*hight > sta[x] || !(*hight | sta[x])) {
            sta[x + 1] = *hight;
            *len += x;
            *top += x == *top ? 1 : 0;
            break;
        }
}

int main() {
    int n, top = 0, maxnum = 0;
    scanf("%d", &n);
    int len[3000]={}, arr[n];

    for (int i = 0; i < n; i++) {   //求左端不下降子序列长度
        scanf("%d", arr + i);
        search(arr + i, &top, len + i);
    }
    top = 0;
    for (int i = n - 1; i >= 0; i--) {  //求右端不下降子序列长度
        search(arr + i, &top, len + i);
        if (len[i] + 1 > maxnum)
            maxnum = len[i] + 1;
    }
    printf("%d\n", n - maxnum); //输出结果
}

发表于 2023-03-21 11:33:00 回复(1)

兜兜3

#include <stdio.h>
#include <string.h>

#define MAXN 3000

static int N;
static int tall[MAXN];
static int dpl[MAXN], dpr[MAXN];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &tall[i]);
    }
    
    for (int i = N - 1; i >= 0; i--) {
        for (int j = N - 1; j > i; j--) {
            dpr[i] = tall[j] < tall[i] ? max(dpr[i], dpr[j] + 1) : dpr[i];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            dpl[i] = tall[j] < tall[i] ? max(dpl[i], dpl[j] + 1) : dpl[i];
        }
    }

    int resK = 0;
    for (int i = 0; i < N; i++)
        resK = max(resK, dpr[i] + dpl[i] + 1);

    printf("%d", N - resK);
    return 0;
}

发表于 2023-02-27 17:03:17 回复(0)

好久不见，最近好吗

#include <stdio.h>
#include <stdlib.h>

int inc_dp[3072];//最大递增序列
int dec_dp[3072];//最小递增序列
int max(int a,int b)
{
return (a>b?a:b);
}
int main(void)
{
int n;
int h[3072];
int i = 0,j=0;
int fo_num = 0;
int dp_max= 0;
while(scanf("%d",&n)!= EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&h[i]);
inc_dp[i]=dec_dp[i] = 1;//包括自己至少有一个
}
for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
{
if(h[i]>h[j] && inc_dp[i] < (inc_dp[j]+1) )
{
inc_dp[i]= (inc_dp[j]+1);
}
}
}
for(i=n-2;i>=0;i--)
{
for(j=i+1;j<n;j++)
{
if(h[i]>h[j] && dec_dp[i] < (dec_dp[j]+1))
{
dec_dp[i] = (dec_dp[j]+1);
}
}
}
for(i = 0;i<n;i++)
{
dp_max = max(dp_max,inc_dp[i]+dec_dp[i] -1);
}
fo_num = n-dp_max;
printf("%d\n",fo_num);
}
return 0;
}

发表于 2022-07-01 09:06:43 回复(0)

练习时长的代码练习生

动态规划:时间复杂度O(n^2)

#include <stdio.h>
#include <string.h>

int main(){
    int N;scanf("%d",&N);
    int a[N];int max;
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    //逆序遍历，以当前元素为基准，记录其右边的最大严格递减序列的元素个数
    int dp_r[N];memset(dp_r,0,sizeof(dp_r));
    for(int i=N-2;i>-1;i--){
        max=-1;
        for(int j=i+1;j<N;j++){
            if(a[i]>a[j] && dp_r[j]>max){
                max=dp_r[j];
                dp_r[i]=dp_r[j]+1;
            }
        }
    }
    //顺序遍历，以当前元素为基准，记录其左边的最大严格递增序列的元素个数
    int dp_l[N];memset(dp_l,0,sizeof(dp_l));
    for(int i=1;i<N;i++){
        max=-1;
        for(int j=i-1;j>-1;j--){
            if(a[i]>a[j] && dp_l[j]>max){
                max=dp_l[j];
                dp_l[i]=dp_l[j]+1;
            }
        }
    }
    //遍历整个数组，计算当前元素dp_r[i]+dp_l[i]的大小，计算最大值
    for(int i=0;i<N;i++){
        if(dp_r[i]+dp_l[i]>max){
            max=dp_r[i]+dp_l[i];
        }
    }
    printf("%d",N-max-1);
}

建立辅助数组，维持辅助数组元素有序排列，用二分查找找到原数组元素在该辅助数组中该插入的位置，该位置即为动态规划中dp[i]的值，时间复杂度O(nlogn)

#include <stdio.h>
#include <string.h>

int search(int* a,int key,int high){//二分查找
    int low=0,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(a[mid]==key){
            return mid;
        }
        else if(a[mid]>key){
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    if(a[mid]>key){
        return mid;
    }
    else{
        return mid+1;
    }
}

int main(){
    int N;scanf("%d",&N);
    int a[N];int b[N];memset(b,0,sizeof(b));//辅助数组
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    int max=0;int p;
    //顺序遍历，以当前元素为基准，记录其左边的最大严格递增序列的元素个数
    int dp_l[N];dp_l[0]=0;
    b[max]=b[0]=a[0];
    for(int i=1;i<N;i++){
        if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
            dp_l[i]=0;
            b[0]=a[i];
        }
        else if(a[i]>b[max]){//原数组元素值超过辅助数组上界，将其插入后形成新的上界
            dp_l[i]=++max;
            b[max]=a[i];
        }
        else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
            p=search(b,a[i],max);
            dp_l[i]=p;
            b[p]=a[i];
        }
    }
    max=0;
    //逆序遍历，以当前元素为基准，记录其右边的最大严格递减序列的元素个数
    int dp_r[N];dp_r[N-1]=0;memset(b,0,sizeof(b));
    b[max]=b[0]=a[N-1];
    for(int i=N-2;i>-1;i--){
        if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
            dp_r[i]=0;
            b[0]=a[i];
        }
        else if(a[i]>b[max]){//原数组元素值超过辅助数组上界，将其插入后形成新的上界
            dp_r[i]=++max;
            b[max]=a[i];
        }
        else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
            p=search(b,a[i],max);
            dp_r[i]=p;
            b[p]=a[i];
        }
    }    
    //遍历整个数组，计算当前元素dp_r[i]+dp_l[i]的大小，计算最大值
    for(int i=0;i<N;i++){
        if(dp_r[i]+dp_l[i]>max){
            max=dp_r[i]+dp_l[i];
        }
    }
    printf("%d",N-max-1);
}

发表于 2022-06-08 16:43:53 回复(0)

已注销

#include <stdio.h>
#define    N    3000
int main()
{
    int height[N],left[N]={0},right[N]={0},n,i,j,flag,max=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&height[i]);
    //从左到右寻找递增子列
    for(i=0;i<n;i++)
    {
        flag=0;
        if(i==0)
            left[i]=1;
        else
        {
            for(j=0;j<i;j++)
            {
                if(height[i]>height[j]&&left[j]+1>left[i])
                {
                    left[i]=left[j]+1;
                    flag=1;
                }
                else if(flag==0)
                    left[i]=1;
            }
        }
    }
    //从右往左寻找递增子列
    for(i=n-1;i>=0;i--)
    {
        flag=0;
        if(i==n-1)
            right[i]=1;
        else
        {
            for(j=n-1;j>i;j--)
            {
                if(height[i]>height[j]&&right[j]+1>right[i])
                {
                    right[i]=right[j]+1;
                    flag=1;
                }
                else if(flag==0)
                    right[i]=1;
            }
        }
    }
    for(i=0;i<n;i++)
        left[i]+=right[i]-1;
    for(i=0;i<n;i++)
        if(left[i]>max)
            max=left[i];
    printf("%d\n",n-max);
    return 0;
}

发表于 2022-04-25 16:54:04 回复(0)

牛客735570582号

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int num;
    int i,j;
    while(scanf("%d",&num)!=EOF)
    {
        int *qu=(int *)malloc(sizeof(int)*num);
        for(i=0;i<num;i++)
        {
            scanf("%d",&qu[i]);
        }
        int *dp1=(int *)malloc(sizeof(int)*num);
        for(i=0;i<num;i++)
        {
            dp1[i]=1;
            for(j=0;j<i;j++)
            {
                if(qu[j]<qu[i])
                {
                    dp1[i]=dp1[i]>(dp1[j]+1)?dp1[i]:(dp1[j]+1);
                }
            }
        }
        int *dp2=(int *)malloc(sizeof(int)*num);
        for(i=num-1;i>=0;i--)
        {
            dp2[i]=1;
            for(j=num-1;j>i;j--)
            {
                if(qu[j]<qu[i])
                {
                    dp2[i]=dp2[i]>(dp2[j]+1)?dp2[i]:(dp2[j]+1);
                }
            }
        }
        int max=dp1[0]+dp2[0];
        for(i=1;i<num;i++)
        {
            max=max>(dp1[i]+dp2[i])?max:(dp1[i]+dp2[i]);
        }
        printf("%d\n",num-max+1);
    }
    return 0;
}

发表于 2021-07-15 13:41:02 回复(0)