首页 > 试题广场 >

小美的数组删除

[编程题]小美的数组删除

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

$\,\,\,\,\,\,\,\,\,\,$ 小美有一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ ，他可以对数组进行如下操作：
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ ● 删除第一个元素 $a_1$ ，同时数组的长度减一，花费为 $x$ 。

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ ● 删除整个数组，花费为 $k\times \operatorname{MEX}(a)$ （其中 $\operatorname{MEX}(a)$ 表示 $a$ 中未出现过的最小非负整数。例如 $[0,1,2,4]$ 的 $\operatorname{MEX}$ 为 $3$ ）。

$\,\,\,\,\,\,\,\,\,\,$ 小美想知道将 $a$ 数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入三个正整数  代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。
第二行输入  个整数 ，表示数组元素。
除此之外，保证所有的  之和不超过 。

输出描述:

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

示例1

输入

1
6 3 3
4 5 2 3 1 0

输出

说明

若不执行操作一就全部删除，，花费  ；
若执行一次操作一后全部删除，，花费  ；
若执行两次操作一后全部删除，，花费  ；
若执行三次操作一后全部删除，，花费  ；
若执行四次操作一后全部删除，，花费  ；
若执行五次操作一后全部删除，，花费  ；
若执行六次操作一，，花费  ；

算法知识视频讲解

Python

在考古的熊

T = int(input())
# print('T is ', T)
for _ in range(T):
    line2 = [int(i) for i in input().split()]
    # print('line2 is ', line2)

    n = line2[0]
    k = line2[1]
    x = line2[2]
    # print('n k x is ', n, k, x)

    line3 = [int(i) for i in input().split()]
    # print('line3 is ', line3)

    mex = [0]*len(line3)

    min_num = 0
    while min_num in set(line3):
        min_num += 1

    mex[0] = min_num
    cost = k*mex[0]

    for j in range(1, len(line3)):
        if line3[j-1] < min_num and line3[j-1] not in set(line3[j:]):            
            min_num = line3[j-1]
            mex[j] = min_num
        else:
            mex[j] = min_num
        
        cost = min(cost, j*x + k*mex[j])

    print(cost)

正向遍历

发表于 2025-07-08 14:17:09 回复(0)

Python

StarryChen

import sys
num = input()
num = int(num) for i in range(num):
    inp = input()
    inp = inp.split()
    number = int(inp[0])
    allcost = int(inp[1])
    cost = int(inp[2])
    arr = input()
    arr = arr.split() for j in range(len(arr)):
        arr[j] = int(arr[j])
    num_set = set(arr)
    n = len(num_set) for j in range(n + 1): if j not in num_set:
            mex = j break  mincost = allcost * mex for j in range(number): if arr[j] > mex: continue  else:
            num_set = set(arr[j + 1:]) if arr[j] not in num_set:
                mex = arr[j]
                fincost = cost * (j + 1) + mex * allcost
                mincost = min(mincost, fincost)
    mincost = min(number * cost, mincost) print(mincost)

发表于 2025-05-16 21:35:21 回复(0)

Python

鸠酒

有没有uu帮我看看这个为什么17/20

t = int(input())

def mex(a):

num_set = set(a)

i = 0

whilei in num_set:

i += 1

returni

for_ in range(t):

n,k,x = map(int,input().strip().split())

arr = list(map(int,input().strip().split()))

# 代表执行i次后全部删除

m = mex(arr[:]) # 当前最小非负整数位置

res = min(n*x,m*k)

fori in range(1,n):

ifarr[i-1] < m:

m = arr[i-1]

res = min(res,k*m+x*i)

print(res)

# 17/20

编辑于 2025-04-04 17:15:59 回复(0)

Python

姚彦梦

有人用Python写吗？实在不知道那里的问题，第17个样例的最后一个报错了。

import sys
T=int(input())

def MEX(array):
    if len(array) == 0:
        return 0
    max_element = max(array)
    for i in range(max_element+1):
        if i not in array:
            nonnegative = i
            break
    else:
        nonnegative = max_element + 1

    return nonnegative

for i in range(T):
    cost = 1e25
    para = sys.stdin.readline().strip()
    n,k,x = map(int, para.split())

    array = list(map(int, sys.stdin.readline().strip().split()))
    
    nonnegative = MEX(array)
    for j in range(n+1):
        new_cost = x*j + k * nonnegative
        
        if new_cost < cost:
            cost = new_cost
        if len(array)!=0:
            if array[0] < nonnegative:
                nonnegative = array[0]
            array.pop(0)

    print(cost)

编辑于 2024-09-23 11:38:55 回复(3)

提交观点

问题信息

难度：

4条回答 280收藏 3528浏览

小美的数组删除

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题