首页 > 试题广场 >

合唱队

[编程题]合唱队

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

$\hspace{15pt}$ 音乐课上，老师将 $n$ 位同学排成一排。老师希望在不改变同学相对位置的前提下，从队伍中选出最少数量的同学，使得剩下的同学排成合唱队形。
$\hspace{15pt}$ 记合唱队形中一共有 $k$ 位同学，记编号为 $1,2,\dots,k$ ，第 $i$ 个人的身高为 $h_i$ 。要求：存在一位同学编号为 $i \left(1 < i < k\right)$ ，使得 $h_1,h_2,\dots,h_{i-1}$ 严格递增，且 $h_{i+1},h_{i+2},\dots,h_k$ 严格递减；更具体地，合唱队形呈 $h_1 < h_2 < \cdots < h_{i-1} < h_i$ 、 $h_i > h_{i+1} > \cdots > h_k$ 。
$\hspace{15pt}$ 你能帮助老师计算，最少需要出列多少位同学，才能使得剩下的同学排成合唱队形？

输入描述:

第一行输入一个整数  代表同学数量。
第二行输入  个整数  代表每一位同学的身高。

输出描述:

输出一个整数，代表最少需要出列的同学数量。

示例1

输入

8
186 186 150 200 160 130 197 200

输出

说明

在这个样例中，有且仅有两种出列方式，剩下的同学分别为  和  。

算法知识视频讲解

千墨

#include <stdio.h>

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

int main() {

int i,j,num=0;

int max=0;

while (scanf("%d", &num) != EOF) { // 注意 while 处理多个 case

int arr[num];

int left[num];

int right[num];

int result[num];

for (i=0;i<num;i++)

scanf("%d", &arr[i]);

//计算节点i的最大左递增子序列，存放于left[i]

for (i=0;i<num;i++){

left[i]=1; //初始化每一个节点的左递增子序列为1 <=> 当前节点自己

for (j=0;j<i;j++){

if (arr[j]< arr[i]) //i左边发现一个节点j

left[i] = max(left[j]+1, left[i]); //动态规划，取左边所有left[j]+1的最大值，作为left[i]。

}

//计算节点i的最大右递减子序列，存放于right[i]

for (i=num-1;i>=0;i--){

right[i]=1; //初始化每一个节点的右递减子序列为1 <=> 当前节点自己

for(j=num-1;j>i;j--){

if (arr[i]>arr[j]) //i右边发现一个节点j

right[i] = max(right[j]+1, right[i]);

}

//合并取的当前节点i的最大队形数目

for(i=0;i<num;i++)

result[i] = left[i]+right[i]-1; //当前节点i在left和right重复计数，需-1

//找出全节点的最大值

for(i=0;i<num;i++)

max = max(result[i], max);

printf("%d", num - max); //剔除的节点数

}

return 0;

}

发表于 2024-06-17 15:25:05 回复(0)

牛客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)