首页 > 试题广场 >

合唱队

[编程题]合唱队

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

输出

说明

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

算法知识视频讲解

Python 3

牛客123074850号

import bisect

def max_l(l, dp):
    b = [float("inf")] * len(l)  # 初始化递增序列
    for i in range(len(l)):
        pos = bisect.bisect_left(b, l[i])  # 找到插入位置
        b[pos] = l[i]  # 更新递增序列
        dp[i] = pos + 1  # 更新 dp
    return dp

def max_r(l, dp):
    b = [float("inf")] * len(l)  # 初始化递增序列（倒序处理递减序列）
    for i in range(len(l) - 1, -1, -1):
        pos = bisect.bisect_left(b, l[i])  # 找到插入位置
        b[pos] = l[i]  # 更新递增序列
        dp[i] = pos + 1  # 更新 dp
    return dp

# 主程序
while True:
    try:
        n = int(input())
        l = list(map(int, input().split()))
        
        # 边界条件处理
        if n == 1:
            print(0)
            continue
        
        left = [0] * n
        right = [0] * n

        left = max_l(l, left)
        right = max_r(l, right)

        max_val = 0
        for i in range(n):
            max_val = max(max_val, left[i] + right[i] - 1)
        
        print(n - max_val)  # 输出最少需要移除的人数
    except EOFError:
        break

发表于 2025-01-08 14:56:45 回复(0)

Python 3

_Mukuro

def bs(ends, size, k):

l, r, ans = 0, size - 1, -1

while l <= r:

mid = (l + r) // 2

if ends[mid] >= k:

ans = mid

r = mid - 1

else:

l = mid + 1

return ans

def find_chorus(n, heights):

dp, ends = [0] * n, [0] * n

size, find = 0, -1

for i in range(0, n):

find = bs(ends, size, heights[i])

if find == -1:

ends[size] = heights[i]

size += 1

dp[i] = size

else:

ends[find] = heights[i]

dp[i] = find

return dp

N = int(input().strip())

heights = list(map(int, input().strip().split(" ")))

dp1, dp2 = find_chorus(N, heights), find_chorus(N, heights[::-1])[::-1]

ans = 0

for i in range(N):

ans = max(ans, dp1[i] + dp2[i] - 1)

print(N - ans)

发表于 2024-08-12 04:20:30 回复(0)

Python 3

清风19

提供一份python的代码

def judge(N,list_h):

dp=[1]*len(list_h)

list_h_1=list(reversed(list_h))

dp1=[1]*len(list_h)

for i in range(len(list_h)):

temp=1

for j in range(i):

if list_h[j]<list_h[i]:

temp=max(temp,dp[j]+1)

dp[i]=temp

for i in range(len(list_h)):

temp1=1

for j in range(i):

if list_h_1[j]<list_h_1[i]:

temp1=max(temp1,dp1[j]+1)

dp1[i]=temp1

maxCount=1

for i in range(len(list_h)):

num=dp[i]+dp1[len(list_h)-i-1]

maxCount=max(num,maxCount)

return maxCount

if __name__ == '__main__':

N=int(input())

height=input()

h=height.split(' ')

list_h=[0]*len(h)

for i in range(len(h)):

list_h[i]=int(h[i])

c=judge(N,list_h)

print(len(list_h)-c+1)

发表于 2023-12-31 03:30:24 回复(0)

Python 3

恶作剧之神阿蒙

import bisect

def inc_max(s):
    q = []
    dp=[]
    for n in s:
        idx = bisect.bisect_left(q, n)
        dp.append(idx+1)
        if idx == len(q):
            q.append(n)
        else:
            q[idx] = n
    return dp


N = int(input())
s = list(map(int, input().split()))
left_s = inc_max(s)  # 从左至右
right_s = inc_max(s[::-1])[::-1]  # 从右至左
sum_s = [left_s[i] + right_s[i] - 1 for i in range(len(s))]  # 相加并减去重复计算
print(str(N - max(sum_s)))


#总感觉题解中使用二分法很勉强，看的迷迷糊糊的，感觉这样写会比较明白一些

发表于 2023-02-21 18:09:54 回复(0)

Python 3

在喝茶的咸鱼很温柔

n = int(input())
list1 = list(map(int, input().split()))

def LengthOfLis(lt):  # 定义函数找出最长递增子序列长度
    if not lt:
        return 1
    lt2 = lt[::-1]  # 反向找最长递增子序列
    dp = [1 for _ in range(len(lt))]
    dp2 = [1 for _ in range(len(lt))]
    for i in range(1, len(lt)):  # 找左边最长
        for j in range(i):
            if lt[j] < lt[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    for i in range(1, len(lt2)):  # 找右边最长
        for j in range(i):
            if lt2[j] < lt2[i]:
                dp2[i] = max(dp2[i], dp2[j] + 1)
    dp3 = list(map(lambda x, y: x + y, dp2[::-1], dp))  # 左边加右边 为总长度+重复一项
    return dp3

print(n - max(LengthOfLis(list1)) + 1)  # 原长度-（最长+1），再+1为减去的长度

发表于 2022-12-22 15:14:29 回复(0)

Python 3

最喜欢春天的修勾很贪睡

用函数打包就不超时，不打包就超时，谁能告诉我这是为什么

发表于 2022-11-24 19:20:57 回复(0)

Python 3

木有粗面201904101731812

二分arr，本质上是最长上升子序列的变体

# 关键点，不再使用遍历找最大值的方法，直接使用二分法维护一个排好序的数组
# 时间复杂度为O(nlog(n))
import bisect

n = int(input())
nums = list(map(int, input().split()))

def dpHelper(nums):
    n = len(nums)
    arr = [nums[0]]
    dp = [1]*n
    
    for i in range(1,n):
        if nums[i] > arr[-1]:
            arr.append(nums[i])
            dp[i] = len(arr)
        else:
            # 此处使用二分查找，将该nums[i]插入到序列中，同时dp[i]为插入的位置+1
            # 为什么不用insort,因为arr更像是正常查询时得到数组的叠加状态，仅服务于后面的查询
            index = bisect.bisect_left(arr, nums[i]) 
            arr[index] = nums[i]
            dp[i] = index + 1
    return dp

dpleft = dpHelper(nums)
dpright = dpHelper(nums[::-1])[::-1]

res = 0
for i in range(n):
    tres = dpleft[i] + dpright[i] - 1
    if res < tres:
        res =  tres
print(n - res)

发表于 2022-08-31 17:03:22 回复(0)

Python 3

牛客555680711号

# def solution(nums): #基础动态规划，O(n*n) 超时
#     n = len(nums)
#     if n <= 2: return 0
#     dp = [[1,1] for _ in range(n)] #0 上升，1 下降
#     maxL = 1
#     for i in range(1,n):
#         for j in range(i-1,-1,-1):
#             if nums[i] > nums[j]:
#                 dp[i][0] = max(dp[i][0],dp[j][0]+1)
#             elif nums[i] < nums[j]:
#                 dp[i][1] = max(dp[i][1],dp[j][1]+1,dp[j][0]+1)
#         maxL = max(maxL,dp[i][0],dp[i][1])
#     return n-maxL
import bisect #利用二分查找优化，dp含义改变为递增子序列
def ascMax(nums,dp): #O(nlogn)
    dp += [1]
    b = [float('inf') for _ in range(len(nums))]
    #b[i]代表当前长度为i+1的递增子序列中，结尾值最小为b[i]
    b[0] = nums[0]
    for i in range(1,len(nums)):
        pos = bisect.bisect_left(b,nums[i]) #找到使b保持严格升序的插入点
        b[pos] = nums[i] #插入
        dp += [pos+1] #记录以num[i]结尾的最长递增子序列
while True:
    try:
        n = int(input())
        nums = list(map(int,input().split()))
        dp1,dp2 = [], []
        ascMax(nums,dp1) #获得最长递增子序列
        ascMax(nums[::-1],dp2) ##获得最长递减子序列
        dp2 = dp2[::-1]
        maxVal = 1
        for i in range(n):
            maxVal = max(maxVal,dp1[i]+dp2[i]-1) #以nums[i]为最大值的合唱队长度
        print(n - maxVal)
    except:
        break

发表于 2022-08-24 21:31:32 回复(0)

Python 3

呵呵hhhh

n = int(input())
seq = list(map(int,input().split()))

def lis(sequence):
    dp, sort = [1], []
    for s in sequence:
        if not sort:
            sort.append(s)
        else:
            if sort[-1] < s:
                sort.append(s)
                dp.append(len(sort))
                continue
            i, j = 0, len(sort) - 1
            #二分搜索 sort 中第一个大于等于s的数字并替换
            while i <= j :
                n = (i + j) // 2
                if sort[n] < s:
                    i = n + 1
                elif sort[n] > s:
                    j = n - 1
                else:
                    i = n 
                    break
            sort[i] = s
            # i + 1 即为 以s结尾的最长递增子序列的长度
            dp.append(i+1)
    return dp
        
# 正反各一遍
inc = lis(seq)
deq = lis(seq[::-1])[::-1]
# 去掉首位，因为序列中最大数的左右两边都要有递减序列，不能为空
print(n - max([inc[i]+deq[i]-1 for i in range(1,n-1)]))

Longest Increasing Subsequence（最长递增子序列）的O(nlogn)解法

发表于 2022-07-14 19:37:06 回复(0)

Python 3

liangzhengjie

不知道为啥超时了，是不是python太慢了

s_len = int(input())
s_arr = [int(i) for i in input().strip().split(' ')]

left_up = []
right_down = []

def countleftup(arr:list):
    longest = 0
    dp = [1 for i in range(len(arr))]
    for i,v1 in enumerate(arr, 0):
        for j,v2 in enumerate(arr[:i], 0):
            if v1 > v2:# can up
                dp[i] = max(dp[i], dp[j] + 1)
                longest = max(longest, dp[i])
    return dp

def countrightdown(arr:list):
    longest = 0
    dp = [1 for i in range(len(arr))]
    temp_index = [i for i in range(len(arr))]
    temp_index.reverse()
    for i in temp_index:# 一级索引为i
        for j,v in enumerate(arr[i + 1:], 0): # 二级索引为i + j，部分为：【i + 1:】
            if v < arr[i]:# 如果一级值大于二级值
                dp[i] = max(dp[i], dp[i + j + 1] + 1)
                longest = max(dp[i], longest)
    return dp

min_out = len(s_arr) - 1
left_up = countleftup(s_arr)
right_down = countrightdown(s_arr)
for i,v in enumerate(s_arr, 0):
    left_max = 0
    right_max = 0
    for j,v_left in enumerate(left_up[:i]):
        if s_arr[j] < v:
            left_max = max(left_max, v_left)
    for j,v_right in enumerate(right_down[i + 1:]):
        if s_arr[j] < v:
            right_max = max(right_max, v_right)
        
    out = len(s_arr) - left_max - right_max - 1
    min_out = min(min_out, out)
# print(left_up)
# print(right_down)
print(min_out)

发表于 2022-06-25 18:08:01 回复(0)

Python 3

牛客862164075号

def left_max(l):
    # 使用自己的长度1初始化dp数组
    # dp表示第i个人前面最大升序列的长度
    dp = [1] * len(l)
    for i in range(len(l)): # 遍历队列中的每一个人
        for j in range(i): # 遍历当前人前面的每一个人
            # 如果当前人前面的人比当前人高，并且当前人前面的最大升序列长度
            if l[j]<l[i] and dp[j]+1>dp[i]:
                dp[i]+=1
    return dp

while True:
    try:
        N = int(input())
        ss = list(map(int, input().split()))
        left_ss = left_max(ss)
        right_ss = left_max(ss[::-1])[::-1]
        sum_s = []
        for i in range(len(left_ss)):
            sum_s.append(left_ss[i]+right_ss[i]-1)
        print(str(N-max(sum_s)))
    except:
        break

大神“MIN大小姐”的题解非常有效。我来讲讲我对状态转移方程的认识。dp[i]状态数组表示在第i个人及其前面、满足升序列的最大长度。dp数组用1初始化，表示当前只考虑自己。状态转移方程if l[j]<l[i]表示前面的人比自己矮，dp[j]+1>dp[i]表示在当前人前面有和自己前面相同数量的最大升序列。因此if l[j]<l[i] and dp[j]+1>dp[i]表示当前人比之前的人高，并且当前人的前面的人有和当前人前面一样长度的上升序列。所以当前人的状态变为dp[i]+1

发表于 2022-06-25 10:06:36 回复(0)

Python 3

0x牛客

不知道 提交的时候为什么错，自测都对的。
n = int(input())
lst = []
while True:
    try:
        lst = list(map(int,input().split()))
        inc = []
        for i in range(len(lst)):
            tmp = []
            tmp.append(lst[i])
            flag = 0
            for j in range(i+1,len(lst)):
                if lst[j] > tmp[-1]:
                    tmp.append(lst[j])
                    flag = j
            if flag != 0:
                for j in range(flag,len(lst)):
                    if lst[j] < tmp[-1]:
                        tmp.append(lst[j])
            inc.append(tmp)
        inc.sort(key=len)
        print(len(inc[-1]))
    except:

发表于 2022-05-22 11:10:55 回复(0)

Python 3

HeartBeating

# 动态规划
def lengthOfLIS(lst):
    dp = []
    for i in range(len(lst)):
        dp.append(1)
        for j in range(i):
            if lst[i] > lst[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp # 每人左边可以站的人数

while True:
    try:
        n, heights = int(input()), list(map(int, input().split()))
        # dp1:每人左边可以站的人数，dp2:每人右边可以站的人数
        dp1, dp2 = lengthOfLIS(heights), lengthOfLIS(heights[::-1])[::-1]
        res = []
        for i in range(len(dp1)):
            res.append(dp1[i] + dp2[i] - 1)
        print(n-max(res))
    except:
        break

发表于 2022-05-09 16:12:16 回复(0)

Python 3

莫理

头大，python不用二分法可否

发表于 2022-05-08 19:24:13 回复(0)

Python 3

鱼説

def shenxu(l):
n=len(l) # 传入list的长度
dp=[1 for i in range(n)] #此列表将记录每个元素之前，算上他本身的升序元素总数
for i in range(n):
for j in range(i):
if l[j]<l[i] and dp[j]+1 > dp[i]:
dp[i]=dp[j]+1 #将求出开始到每个元素位置上最长升序的元素个数
return dp
while 1:
try:
a=int(input())
b=[int(i) for i in input().split()]
b1=b[::-1]
dp=shenxu(b) #求每个元素的左侧最长升序元素个数集合包含自己
dp1=shenxu(b1)[::-1] #求每个元素右侧最长降序的元素个数集合，包含自己
lst=[]
for j in range(a):
lst.append(dp[j]+dp1[j]-1) #升降计算中多算了一次自己减去
print(a-max(lst))
except:
break

发表于 2022-04-27 20:55:23 回复(0)

Python 3

牛客835424683号

N²超时？不理解，只要是小于1E8就可以的吧？

发表于 2022-04-07 19:41:32 回复(0)

Python 3

磨洋工匠人e

看半天没明白dp[i] = pos+1，这句其实没用

发表于 2022-03-12 13:15:23 回复(0)

Python 3

牛客693600570号

#最烦的莫过是代码写对了，自测运行都通过了，提交时没有输出，还不告诉你原因，不知道是什么原因，希望有哪位大佬给我看下
def dfx(b):
    c =[]
    d =[]
    for i, _ in enumerate(b):
        if c == []:
            c.append(_)
            d.append(len(c))
        else:
            if _ > max(c):
#                 print(_)
                c.append(_)
                d.append(len(c))
            else:
                for j, __ in enumerate(c):
                    if _ <=__ :
                        c[j] = _
                        d.append(len(c))
                        break
    return (c,d)

while True:
    try:
        a = input()
        b = list(map(int,input().split(" ")))
    except Exception as e:
#         print(e)
        break
    else:
        c1 = dfx(b)
        b.reverse()
        c2 = dfx(b)
        c2[1].reverse()
        for i, _ in enumerate(c1[1]):
            c1[1][i] = _ + c2[1][i]
        print(int(a)-max(c1[1]) +1)

发表于 2022-03-10 15:00:59 回复(0)