题解 | #合唱队#

合唱队

https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

解题思路

  1. 这是一道最长上升下降子序列问题
  2. 对于每个位置i,需要求:
    • 左边的最长上升子序列长度(LIS)
    • 右边的最长下降子序列长度(LDS)
  3. 最后用总人数减去最大的(LIS + LDS - 1)即为需要出列的最少人数

代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> heights(n);
        for (int i = 0; i < n; i++) {
            cin >> heights[i];
        }
        
        // 计算每个位置左边的最长上升子序列长度
        vector<int> left(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (heights[i] > heights[j]) {
                    left[i] = max(left[i], left[j] + 1);
                }
            }
        }
        
        // 计算每个位置右边的最长下降子序列长度
        vector<int> right(n, 1);
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j > i; j--) {
                if (heights[i] > heights[j]) {
                    right[i] = max(right[i], right[j] + 1);
                }
            }
        }
        
        // 找出最大的合唱队形长度
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = max(maxLen, left[i] + right[i] - 1);
        }
        
        // 需要出列的最少人数
        cout << n - maxLen << endl;
    }
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = sc.nextInt();
            }
            
            // 计算每个位置左边的最长上升子序列长度
            int[] left = new int[n];
            Arrays.fill(left, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (heights[i] > heights[j]) {
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }
            
            // 计算每个位置右边的最长下降子序列长度
            int[] right = new int[n];
            Arrays.fill(right, 1);
            for (int i = n-1; i >= 0; i--) {
                for (int j = n-1; j > i; j--) {
                    if (heights[i] > heights[j]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }
            
            // 找出最大的合唱队形长度
            int maxLen = 0;
            for (int i = 0; i < n; i++) {
                maxLen = Math.max(maxLen, left[i] + right[i] - 1);
            }
            
            System.out.println(n - maxLen);
        }
    }
}
while True:
    try:
        n = int(input())
        heights = list(map(int, input().split()))
        
        # 计算每个位置左边的最长上升子序列长度
        left = [1] * n
        for i in range(n):
            for j in range(i):
                if heights[i] > heights[j]:
                    left[i] = max(left[i], left[j] + 1)
        
        # 计算每个位置右边的最长下降子序列长度
        right = [1] * n
        for i in range(n-1, -1, -1):
            for j in range(n-1, i, -1):
                if heights[i] > heights[j]:
                    right[i] = max(right[i], right[j] + 1)
        
        # 找出最大的合唱队形长度
        max_len = max(left[i] + right[i] - 1 for i in range(n))
        
        print(n - max_len)
    except:
        break

算法及复杂度

  • 算法:动态规划(最长上升/下降子序列)
  • 时间复杂度:,其中n为学生总数
  • 空间复杂度:,需要两个长度为n的数组存储dp值
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
昨天 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务