首页 > 试题广场 >

合唱队

[编程题]合唱队

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

牛客348721693号

# 等回头用二分查找实现一遍
def get_max_up_arr(arr, count_num):
    arr_line = [1]*count_num
    for i in range(count_num):
        for j in range(i):
            if arr[j] < arr[i]:
                arr_line[i] = max(arr_line[i], arr_line[j]+1)
    return arr_line

while True:
    try:
        num_count = input()
        arr = list(map(int,raw_input().split(' ')))
        left_up_arr = get_max_up_arr(arr, num_count)
        right_up_arr = get_max_up_arr(arr[::-1], num_count)[::-1]
        least_num = num_count - max([ i+j-1for i,j in zip(left_up_arr,right_up_arr)])
        print least_num
    except:
        break

发表于 2022-09-02 08:35:00 回复(0)

Python

牛客622181604号

超时只通过40%, 但感觉算法思路应该是对的
while True:
    try:
        N = int(input())
        nums = list(map(int, input().split()))
        f_1 = []   # 每个位置最长左子列长度
        f_2 = []   # 每个位置最长右子列长度
        for i in range(N):
            f_1.append(1)
            f_2.append(1)
        for j in range(1, N):
            for k in range(0, j):
                if nums[j] > nums[k]:
                    f_1[j] = max(f_1[j], f_1[k]+1)
                if nums[N-1-j] > nums[N-1-k]:
                    f_2[N-1-j] = max(f_2[N-1-j], f_2[N-1-k]+1)
        max_q = 1
        for i in range(N):
            max_q = max(max_q, (f_1[i] + f_2[i])-1)
        print(N - max_q)
    except:
        break

编辑于 2021-03-29 23:40:21 回复(0)

Python

牛客44738297号

动态规划和利用单调队列的思想大神们已经讲得很多，本人上传一版自己注释的代码，希望可以对还是不理解此题的朋友有一定帮助

#二分搜索定位函数，自己写此函数，也可用已有库bisect
#搜索元素val在nums中的定位，返回的定位位置i,需满足：
#nums[:i]中所有元素都 < val, nums[i:]中所有元素都 >= val
def binary(nums, val):
    l = 0
    r = len(nums)-1
    while l < r:
        mid = (l + r) // 2
        if nums[mid] == val:
            return mid
        elif nums[mid] > val:
            #为满足开头说的搜索条件和目的，此处一定不能写成 r = mid - 1
            r = mid 
        else:
            l = mid + 1
    return r
#计算以每个位置为中心，得到的左侧可以满足单调要求的人数（不包括自己）
def count(nums):
    #单调递增队列queue，初始为nums[0]
    #每个位置的左侧满足要求的人数count（默认为0）
    queue = [nums[0]]
    count = [0 for _ in range(len(nums))]
    #从1开始遍历即可，因为第一个位置nums[0]左侧无人，count一定为0
    for i in range(1, len(nums)):
        #当nums[i]大于此位置前出现的最大值时，左侧满足要求的人数即为len(queue)
        if nums[i] > queue[-1]:
            count[i] = len(queue)
            queue.append(nums[i])
        #否则，进行二分搜索定位并覆盖旧值
        #在单调递增队列中的定位位置下标 即为其左侧满足要求的人数
        else:
            location = binary(queue, nums[i])
            queue[location] = nums[i]
            count[i] = location
    return count
while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))
        assert(n == len(nums))
        left_count = count(nums)#得到每个位置左侧满足要求的人数
        right_count = count(nums[::-1])[::-1]#得到每个位置右侧满足要求的人数
        max_peple = 1#最大人数初始为1
        for i in range(len(left_count)):
            #当前可组成的最大人数，由于前面计算的左右侧人数不包括自己，需再+1
            cur_peple = 1 + left_count[i] + right_count[i]
            if cur_peple > max_peple:
                max_peple = cur_peple
        print(n - max_peple)
    except:
        break

编辑于 2021-02-18 11:49:08 回复(0)

Python

大溪地渔民

import bisect


def lss(seq):
    temp, res = [float("inf")]*len(seq), []
    for e in seq:
        pos = bisect.bisect_left(temp, e)
        temp[pos] = e
        res.append(pos+1)
    return res


while True:
    try:
        n, heights = int(input()), list(map(int, input().split()))
        lm = lss(heights)
        rm = lss(heights[::-1])[::-1]
        print(n-max(map(sum, zip(lm, rm)))+1)
    except:
        break

发表于 2020-12-22 00:16:05 回复(1)

Python

牛客312920801号

def get_index(nums,target):#二分法排序查找，返回排序位置
low,high=0,len(nums)-1
pos=len(nums)
while low < high:
mid=(low+high)//2
if nums[mid] < target:
low = mid+1
else:
high = mid
pos = mid
return pos
#创建列表，从左到右查找出列表的位置，位置加一即是自己左边的人数
def increase_lis(l,res):
n=len(l)
temp=[10**10]*n#创建一个列表来存放排序结果，初始化为最大值
temp[0]=l[0]
res+=[1]
for i in range(1,n):
pos=get_index(temp,l[i])
res+=[pos+1]#记录最大排序人数
temp[pos]=l[i]#更新二分法排序表
return res
while True:
try:
n=int(input())
a=list(map(int,input().strip().split()))
dp_l=increase_lis(a,[])
dp_r=increase_lis(a[::-1],[])[::-1]
maxValue=max([dp_l[i]+dp_r[i]-1 for i in range(n)])
print(n-maxValue)
except:
break

发表于 2020-12-17 18:51:58 回复(0)

Python

公子i吃鱼

while True:
    try:
        n = int(input())
        A = list(map(int, input().split()))
        
        left = [0] * n
        for i in range(1, n):
            for j in range(i):
                if A[j] < A[i] and left[j] + 1 > left[i]:
                    left[i] = left[j] + 1
        
        right = [0] * n
        for i in range(n - 2, -1, -1):
            for j in range(n - 1, i, -1):
                if A[j] < A[i] and right[j] + 1 > right[i]:
                    right[i] = right[j] + 1
        
        ans = 0
        for i in range(n):
            if left[i] > 0 and right[i] > 0:
                if left[i] + right[i] + 1 > ans:
                    ans = left[i] + right[i] + 1

        res = n - ans
        print(res)
    except:
        break

发表于 2020-10-25 17:29:56 回复(1)

Python

牛客740273319号

import bisect

def shouldRemoveLeft(team: list) -> list:
    cur_team = [team[0]]
    removed = [0] * len(team)
    i = 1
    while i < len(team):
        x = team[i]
        pos = bisect.bisect(cur_team, x)
        removed[i] = removed[i-1] + len(cur_team) - pos
        cur_team = cur_team[:pos]
        cur_team.append(x)
        i += 1
    return removed

def numsOfPeopleOutOfTheTeam(team: list) -> int:
    if not team&nbs***bsp;len(team) < 3: return 0
    dp_left = shouldRemoveLeft(team)
    dp_right = shouldRemoveLeft(team[::-1])[::-1]
    
    ans = float('inf')
    for i in range(len(team)):
        ans = min(dp_left[i] + dp_right[i], ans)
    return ans

if __name__ == "__main__":
    import sys
    i = []
    for line in sys.stdin:
        i.append(line)
    ans = numsOfPeopleOutOfTheTeam(i[1].strip().split())
    print(ans)

谁能帮忙看看上面这种做法错在哪里呢？

楼上大部分都是从当前队列里有多少人来考虑的。我则是顺着题目考虑应改去掉多少人。

我的状态定义是：如果选择第i位作为队列中最高的哪位，那么左边应该去掉多少人？二分查找第i位进入左边队列应处于的位置，该位置右侧的人都应该去掉。

状态转移方程：dp[i] = dp[i -1] + 当前队列的长度 - 插入的索引位置

以此类推，右边的应该去掉的人是将队列翻转之后用同样的方式再求一次。

这样的话，最少去掉人数应该是，两个数组同位置求和的最小值。

发表于 2020-10-16 14:50:56 回复(0)

Python

牛客600841328号

基本思想是计算最长递增子数列，可以使用两种方法。第一种 left_most() 函数使用动态规划搜索，时间复杂度为 O(N^2)。第二种 left_most_binary() 使用了二分法搜索，可以将时间复杂度降低至 O(NlogN)。中心思想是设置一个排序数列 dp 来存放 arr 里的数，用二分法搜索每个数 arr[i] 插入 dp 的位置，如果该数需要被插入 dp 末尾位置，就增加 dp 的长度。对每个 arr[i]来说，dp 的长度就是该数左边的最长递增子数列的值。注意 dp 里的数值并不是该递增子数列。

import bisect

def left_most(arr):
    # time: O(n^2), space: O(n)
    ans = [1]*len(arr)
    for i in range(len(arr)):
        for j in range(i):
            if arr[j]<arr[i] and ans[j]+1>ans[i]:
                ans[i] = ans[j]+1
    return ans

def left_most_binary(arr):
    # time: O(nlogn), space: O(n)
    ans = [1]*len(arr)
    dp = []
    for i in range(len(arr)):
        index = bisect.bisect_left(dp, arr[i])
        if index==len(dp): dp.append(arr[i])
        else: dp[index] = arr[i]
        ans[i] = len(dp)
    return ans

while True:
    try:
        n = int(input())
        if not n: break
        h = list(map(int, input().split(' ')))
        left = left_most_binary(h)
        right = left_most_binary(h[::-1])[::-1]
        ans = max([left[i]+right[i]-1 for i in range(n)])
        print (n-ans)

    except: break

发表于 2020-10-02 01:41:56 回复(0)

Python

小狗最6

while 1:
try:
n = int(input())
list_0 = list(map(int, input().split()))
def maxlong(list_):
dp = [1 for i in range(len(list_))]
res = 1
for i in range(len(list_)):
for j in range(i):
if list_[i] > list_[j] and dp[i]<dp[j]+1:
dp[i] = dp[j]+1
return dp
left = maxlong(list_0)
right = maxlong(list_0[::-1])[::-1]
temp = n
for i in range(n):
a = n-(left[i]+right[i]-1)
if a < temp:
temp =a
print(temp)
except:
break

发表于 2020-09-01 19:18:03 回复(0)

Python

一笑冷雨

while True:
    try:
        N, num = int(input()), list(map(int, input().split()))
        dp1, dp2, dp3 = [1]*N, [1]*N, []
        for x in range(1, N):
            for i in range(0, x):
                if num[i] < num[x]: dp1[x] = max(dp1[x], dp1[i] + 1)
        for x in range(N-1, -1, -1):
            for i in range(N-1, x, -1):
                if num[i] < num[x]: dp2[x] = max(dp2[x], dp2[i] + 1)
        for x in range(0,N): dp3.append(N+1-dp1[x]-dp2[x])
        print(min(dp3))
    except:
        break

发表于 2020-08-18 22:52:41 回复(0)

Python

一直爬的蜗牛

def left_max(list):
    """计算出i这个人，包含自己，在左边符合人数的个数"""
    res = [1] * len(list)
    for i in range(len(list)):
        for j in range(i):
            if list[j] < list[i] and res[j] + 1 > res[i]:
                res[i] = res[j] + 1
    return res

def right_max(list):
    """计算出i这个人，包含自己，在右边符合人数的个数"""
    res = [1] * len(list)
    for i in range(len(list))[::-1]:
        for j in range(i+1,len(list)):
            if list[j] < list[i] and res[j] + 1 > res[i]:
                res[i] = res[j] + 1
    return res

while True:
    try:
        n = int(input())
        result = list(map(int,input().split()))
        left = left_max(result)
        right = right_max(result)
        sum_list = []
        for i in range(len(left)):
            sum_list.append(left[i] + right[i])
        print(n - (max(sum_list) - 1))
        
    except:

发表于 2020-05-14 17:55:30 回复(4)

Python

修行中人

def LittleMan(length, highLs):

    leftLs = [1 for i in range(length)]
    rightLs = [1 for i in range(length)]

    # [1, 1, 1, 2, 2, 1, 3, 4]
    for i in range(1, length):
        maxValue = 1
        for j in range(0, i):
            if highLs[i] > highLs[j]:
                if leftLs[j] + 1 > maxValue:
                    maxValue = leftLs[j] + 1
        leftLs[i] = maxValue

    (3739)# [3, 3, 2, 3, 2, 1, 1, 1]           
    for i in range(length-2, -1, -1):
        maxValue = 1
        for j in range(i+1, length):
            if highLs[i] > highLs[j]:
                if rightLs[j] + 1 > maxValue:
                    maxValue = rightLs[j] + 1
        rightLs[i] = maxValue

    allLs = list()
    for i in range(length):
        allLs.append(rightLs[i] + leftLs[i] - 1)
    max_val = max(allLs)
    return length - max_val


if __name__ == "__main__":
    while True:
        try:
            n=int(input())
            s=list(map(int,input().split()))
            res = LittleMan(n, s)
            print(res)
        except:
            break

发表于 2020-03-26 11:56:01 回复(1)

Python

大哥，算了算了

注意动态规划中的一些细节。。。

max函数会增加运行时间导致不能通过。。

def updown(h):
    res = [1 for i in range(len(h))]
    for i in range(len(h)):
        for j in range(i):
            if h[i] > h[j] and res[i] < res[j] + 1:
                res[i] = res[j] + 1
            '''
            死活过不了。。。复杂度一样
            但是估计是用了max函数，所以增加了运行时间。。。
            if h[i] > h[j]:
                res[i] = max(res[i], res[j] + 1)
            '''
    return res


while True:
    try:
        n = int(input())
        hArray = list(map(int, input().split()))
        resleft = updown(hArray)
        resright = updown(hArray[::-1])[::-1]
        res = []
        for i in range(len(hArray)):
            res.append(resleft[i] + resright[i] - 1)

        print(n - max(res))

           
    except:
        break

编辑于 2020-03-23 23:26:33 回复(0)

Python

王小燊

import bisect

#动态规划获得最大递增自序列，时间复杂度O(n*n)
# def ascMax(l, dp):
#     dp += [1]
#     for i in range(1, len(l)):
#         tmp = 0
#         for j in range(0, i):
#             if l[j] < l[i]:
#                 tmp = max(dp[j], tmp)
#         dp += [tmp + 1]

#二分法获取最大递增子序列，时间复杂度O(nlogn)
def ascMax(l, dp):
    dp += [1]
    b = [float('inf') for i in range(len(l))]#初始化b数组为无穷大
    b[0] = l[0](1844)#第一个元素自己就是最大递增子序列
    for i in range(1, len(l)):
        pos = bisect.bisect_left(b, l[i])
        b[pos] = l[i]
        dp += [pos + 1]

while True:
    try:
        N = int(input())
        H = list(map(int, input().split(' ')))
        dp_1, dp_2 = [], []
        ascMax(H, dp_1)
        ascMax(H[::-1], dp_2)
        dp = []
        for i in range(0, N):
            dp += [dp_1[i] + dp_2[N-i-1] - 1]
        print(N - max(dp))
    except:
        break

编辑于 2020-03-09 00:00:46 回复(2)

Python

谢小橙

对于这道题的含义以及解题思路可能有些人不太明白，结合上面几位大佬的解释，提出一下个人见解：

1. 对于题目，我个人理解是所有人都已经站好位，不能再改变位置了，只能从当中去掉人组成合唱队。同时，可以考虑中间的人两边没有人的情况（比如两头的两个人，或者这个人太矮周围的人都比他高的情况），但是这种情况基本被pass掉。

2. 对于1楼大佬所说的最长递增子序列，我个人见解是：

比如题中所给出的示例：186 186 150 200 160 130 197 200，先看每个人的左边可能出现最多的人。首先如果第一个数186在中间，左边没有数，就自己一个人，所以是1；第二个数186因为左边那个人跟他一边高，没有比他矮的了，所以也是1；第三个数150，左边的人都比他高，他如果是中间的话左边也他自己一个人，所以还是1；第四个数200，因为不能换位置，所以只能留186或者150，加上自己，就是2...最后再以197为例，左边保留150,160是左边人最多的情况，再加上自己，就是3。所以每个人左边人做多的情况（加上自己）就是（186）1 1 1 2 2 1 3 4（200）。同理，看一下每个人右边可能出现最多的人，这时我们从后往前看。200在最右面，所以自己一个人，是1；197最右面没有比他矮的，自己，是1...160左边一个比他矮的，所以算上自己是2，以此类推。所以每个人右边人做多的情况（加上自己）就是（186）3 3 2 3 2 1 1 1（200）

3. 所以将上面两个划横线的对应相加，就可以得到自己如果是中间的那个人，可以得到的最大的合唱队人数。当然，自己加了两遍，所以得减掉一个自己。另外题目问的是最少去掉的人，所以最后的结果：

总人数 - 该数所在队列人数 = 需要出队的人数

4. 本人所编代码中最核心的部分是（以左最长递增子序列为例）

if l[j]<l[i] and ans[j]+1>ans[i]:  ans[i]=ans[j]+1

代表的意思是目前的这个ans[j] + 1是否比之前得到的 ans[i] 要大(ans[i]默认是1，表示自己一个人)。假设之前ans[i] = 4,现在ans[j] + 1 = 3,那么就不需要更新。

代码如下：

# 每个人的左边出现的最多人(输出左_最长递增子序列)
def left_max(l):#l为站成一排的同学序列
    ans=[1]*len(l)
    for i in range(len(l)):# 每个人的游标(从前往后)
        for j in range(i):# 这个人前面每个人的游标
            if l[j]<l[i] and ans[j]+1>ans[i]:
                ans[i]=ans[j]+1
    return ans # 1 1 1 2 2 1 3 4

# 每个人的右边出现的最多人(输出右_最长递增子序列)
def right_max(l):
    ans=[1]*len(l)
    for i in range(len(l)-1,-1,-1):# 每个人的游标（从后往前）
        for j in range(i+1,len(l)):# 这个人后面每个人的游标
            if l[j]<l[i] and ans[j]+1>ans[i]:
                ans[i]=ans[j]+1
    return ans # 3 3 2 3 2 1 1 1

while True:
    try:
        N=int(input())(1177)#8
        tall_li_str=input().split()
        tall_li_int=[int(v) for v in tall_li_str]#[186,186,150,200,160,130,197,200]
        left_li=left_max(tall_li_int)
        right_li=right_max(tall_li_int)
        sum_li=[]#left_li和right_li加和，可以得到每个人如果是中间那个人的话，合唱队最长是多少（自己算两遍）
        for i in range(len(left_li)):
            sum_li.append(left_li[i]+right_li[i])
        print(N-max(sum_li)+1)#题中问的是最少去几人，也就是总人数减去合唱队最多人数
        # 另外加和时自己算了两遍，还得再减去一遍
    except:
        break

编辑于 2020-03-01 16:46:01 回复(35)

Python

0b100001101000

import bisect

def deal(l,res):
    b    = [float('inf')]*len(l)
    b[0] = l[0]
    res  = res+[1]
    for i in range(1,len(l)):
        pos =bisect.bisect_left(b,l[i])
        b[pos]=l[i]
        res += [pos+1]
    return res

def main(n,s):
    n = int(n)
    s = list(map(int,s.split()))
    dp1, dp2=[], []
    dp1 =deal(s,dp1)
    dp2 =deal(s[::-1],dp2)[::-1]
    return n-max(map(sum,zip(dp1,dp2)))+1

while 1:
    try:
        print(main(input(),input()))
    except:
        exit()

发表于 2020-02-22 22:25:31 回复(1)

Python

牛客757584655号

NlogN python 版本

用python比较坑的一点是N*N复杂度的动态规划是过不了的(会有50%的case超时)

这里就用二分查找的方式搞个NlogN的写法。

import sys

def lsi(values):
    L = len(values)

    def check(vs):
        index = 0
        L0 = []
        D = [-1] + [2000000000 for i in range(L)]

        for v in vs:
            begin = 0
            end = index
            # 二分查找
            while True:
                if end - begin <= 1:
                    break
                mid = (begin + end) / 2
                if D[mid] >= v:
                    end = mid
                else:
                    begin = mid

            for tmp in (begin, end):
                if D[tmp] < v:
                    index = max(tmp + 1, index)
                    D[tmp + 1] = min(D[tmp + 1], v)

            L0.append(index)
        return L0

    L0 = check(values)
    values.reverse()
    L1 = check(values)

    maxim = 0
    for i in range(L):
        maxim = max(L0[i] + L1[L - i - 1] -1, maxim)

    return max(max(L0), max(L1), maxim)


while True:
    N = sys.stdin.readline().strip()
    if not N:
        break
    values = [int(i) for i in sys.stdin.readline().strip().split(' ')]
    print len(values) - lsi(values)

发表于 2020-02-15 05:52:12 回复(0)

Python

酒千觞

def get_index(nums,target): # 返回列表中不小于目标元素的索引
    low,high=0,len(nums) # 左开右闭区间
    while low<high:
        mid=(low+high)//2
        if nums[mid]<target:
            low=mid+1
        else:
            high=mid
    return low
def increase_lis(l):
    sorted_l = [float('inf') for _ in range(len(l))] #巧妙的实现去重,可以理解为去重有序数组
    res,sorted_l[0] = [1],l[0]
    for i in range(1,len(l)):
        pos=get_index(sorted_l,l[i])
        res.append(pos+1)
        sorted_l[pos] = l[i]
    return res
while True:
    try:
        n=int(input())
        a=list(map(int,input().strip().split()))
        dp_L=increase_lis(a)
        dp_R=increase_lis(a[::-1])[::-1]
        max_value=max([dp_L[i]+dp_R[i]-1 for i in range(n)])
        print(n-max_value)
    except:
        break

参照为啥要起名字那位同学,有序数组初始化为定长是精髓,实现插入时自动去重

编辑于 2020-01-12 14:42:02 回复(1)

Python

l1xnan

用 Python 搞动态规划太容易超时超内存了，用 PyPy 经过 array 优化才跑通：

from array import array
def max_inc_sub(nums=None):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp
while True:
    try:
        total = int(input())
        heights = array("I", [int(h) for h in input().split()])
        inc1 = max_inc_sub(heights)
        inc2 = max_inc_sub(heights[::-1])[::-1]
        _max = 0
        for x1, x2 in zip(inc1, inc2):
            _max = max(_max, x1 + x2)
        print(total - _max + 1)
        # print(total - max([x1 + x2 for x1, x2 in zip(inc1, inc2)]) + 1)
    except Exception as e:
        break

发表于 2020-01-10 18:15:36 回复(2)