首页 > 试题广场 >

合唱队

[编程题]合唱队

热度指数：335443 时间限制：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

输出

说明

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

算法知识视频讲解

Javascript_V8

阿锋.201910102005207

//这里有一个示例需要补充

//8
//1 2 3 1 2 4 5 6

//目前示例没有满足最高不能为头尾

// 左递增，右递减。最高不能为头尾

let n;
function func(height) {
const list = [];
for (let i = 0, l = height.length; i < l; i++) {
list[i] = 1;
for (let j = 0; j <= i; j++) {
if (height[i] > height[j]) {
list[i] = Math.max(list[i], list[j] + 1);
}
}
}
return list;
}
while (n = readline()) {
n = parseInt(n);
let height = readline().split(' ').map(i => parseInt(i));
let list1 = func(height);
let list2 = func(height.reverse()).reverse();
let list3 = list1.map((i, idx) => i + list2[idx]);
let max = 0, idx = -1;
list3.forEach((i, index) => {
if (index !== 0 && index !== list3.length-1 && list1[index]!==1 && list2[index]!==1) {
if (max < i) {
max = i;
idx = index;
}
}
});
//print(max)
//print(list1)
//print(list2)
//print(list3)
console.log(n - (max - 1));
}

发表于 2022-08-31 16:21:41 回复(0)

Javascript_V8

独孤剑走偏锋

动态规划

const N = readline()
const hArr = readline().trim().split(' ').map(i => +i)
const left = []
const right = []
for (let i = 0; i < N; i++) {
    left[i] = right[i] = 1
}
for (let i = 1; i < N; i++) {
    let max = left[i]
    for (let j = i - 1; j >= 0; j--) {
        if (hArr[j] < hArr[i]) {
            max = Math.max(max, left[j] + left[i])
        }
    }
    left[i] = max
}
for (let i = N - 2; i >= 0; i--) {
    let max = right[i]
    for (let j = i + 1; j < N; j++) {
        if (hArr[j] < hArr[i]) {
            max = Math.max(max, right[j] + right[i])
        }
    }
    right[i] = max
}
var res = left.reduce((res, l, i) => {
    return Math.max(res, left[i] + right[i] - 1)
}, 0)
print(N - res)

发表于 2022-07-08 22:53:16 回复(0)

Javascript_V8

阿米诺斯

readline();
let input = readline();
let a = input.split(' ').map(x => parseInt(x));
function c(a) {
  //p[i]:i元素左边的最大递增序列长度
  //q[i]:i元素右边的最大递减序列长度
  let p = [0], q = [];
  q[a.length - 1] = 0;
  for (let i = 1; i < a.length; i++) {
    let max = -1;
    //第i个元素的p值等于 {k| k<i&&a[k]<a[i]}的最大p值+1
    for (let j = 0; j < i; j++) {
      if (a[i] > a[j] && max < p[j]) {
        max = p[j];
      }
    }
    p[i] = max + 1;
  }

  for (let i = a.length - 2; i >= 0; i--) {
    let max = -1;
    //第i个元素的q值等于 {k| k>i&&a[k]<a[i]}的最大q值+1
    for (let j = a.length - 1; j > i; j--) {
      if (a[i] > a[j] && max < q[j]) {
        max = q[j];
      }
    }
    q[i] = max + 1;
  }
  //剩余最大人数
  let max = 0;
  for (let i = 0; i < a.length; i++) {
    max = Math.max(p[i] + q[i] + 1, max);
  }
  //最小出列人数
  return (a.length - max);
}
console.log(c(a));

发表于 2022-07-04 00:59:46 回复(0)

Javascript_V8