首页 > 试题广场 >

气球谜题

[编程题]气球谜题
  • 热度指数：4206 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 n 个气球，摆放成一排，颜色仅为红、黄、蓝中的一种。小红想要让颜色相同的气球连续的摆放在一起，为了达成这个目标，她需要将气球重新染色。第 i 个气球重新染成任意的颜色均需要 t_i 秒，询问需要消耗的最少时间是多少呢。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left( 1\leqq n \leqq 2 \times 10^5 \right) 代表气球数量。
\hspace{15pt}第二行输入一个长度为 n 的、仅由 0,1,2 构成的字符串代表气球的初始颜色。其中，0,1,2 分别代表初始颜色为红、黄、蓝。
\hspace{15pt}第三行输入 n 个整数 t_1,t_2,\dots,t_n \left( 1 \leqq t_i \leqq 10^7 \right) 代表气球重新染色需要的时间。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表最少需要的染色时间。
示例1

输入

5
00000
1 2 3 4 5

输出

0

说明

\hspace{15pt}由于初始时全部气球颜色都是一样的，所以不需要重新进行染色。
示例2

输入

6
210102
1 1 4 5 1 4

输出

3

说明

\hspace{15pt}其中一种最优的染色方案是将气球染色为 \texttt{ ，花费 3 。
示例3

输入

6
001012
1 1 4 5 1 4

输出

3

说明

\hspace{15pt}其中一种最优的染色方案是将气球染色为 \texttt{ ，花费 3 。
算法知识视频讲解
添加回答
Python3
不想上网课的考拉在写文章头像 不想上网课的考拉在写文章
不知道为什么只能过80%的案例
n = int(input())
s = input().strip()
t = list(map(int, input().split()))

# 构造前后缀和数组
prefix = [[0] * (n + 1) for _ in range(3)]
for c in range(3):
for i in range(1, n + 1):
prefix[c][i] = prefix[c][i - 1] + (t[i - 1] if int(s[i - 1]) != c else 0)

suffix = [[0] * (n + 1) for _ in range(3)]
for c in range(3):
for i in range(n - 1, -1, -1):
suffix[c][i] = suffix[c][i + 1] + (t[i] if int(s[i]) != c else 0)

# 单元素最小耗费
min_single = min(prefix[0][n], prefix[1][n], prefix[2][n])

min_double = float("inf")
min_triple = float("inf")

#对给定颜色对计算最小耗费
def update_min_double(c1, c2):
global min_double
current_min = float("inf")
for k in range(n + 1):
cost = prefix[c1][k] + suffix[c2][k]
if cost < current_min:
current_min = cost
if current_min < min_double:
min_double = current_min

#遍历所有色对
for c1 in range(3):
for c2 in range(3):
if c1 != c2:
update_min_double(c1, c2)

#三元色组最小花费计算
def update_min_triple(perm):
global min_triple
c1, c2, c3 = perm
min_diff = [0] * (n + 1)
min_val = float("inf")
for k in range(n + 1):
current = prefix[c1][k] - prefix[c2][k]
if current < min_val:
min_val = current
min_diff[k] = min_val
for k2 in range(n + 1):
cost = min_diff[k2] + prefix[c2][k2] + suffix[c3][k2]
if cost < min_triple:
min_triple = cost

# 遍历所有三元色组
from itertools import permutations

for perm in permutations([0, 1, 2]):
update_min_triple(perm)

result = min(min_single, min_double, min_triple)
print(result)

发表于 2025-06-30 22:07:27 回复(0)
Python3
牛客253153607号头像 牛客253153607号
n=int(input())
color=input().strip()
t=list(map(int,input().split()))
cost0,cost1,cost2=[0]*(n+1),[0]*(n+1),[0]*(n+1)#用来记录将字符串的前i个元素全部转化为指定元素（0，1，2）所需的时间
for i in range(len(color)):
    if color[i]=='0':
        cost0[i+1]=cost0[i]
        cost1[i+1]=cost1[i]+t[i]
        cost2[i+1]=cost2[i]+t[i]
    elif color[i]=='1':
        cost0[i+1]=cost0[i]+t[i]
        cost1[i+1]=cost1[i]
        cost2[i+1]=cost2[i]+t[i]
    elif color[i]=='2':
        cost0[i+1]=cost0[i]+t[i]
        cost1[i+1]=cost1[i]+t[i]
        cost2[i+1]=cost2[i]
def fun(color0,color1,color2):
    #我们要找到i,j两个切点将字符串分成三段，分别换成（0，1，2）的一种排列，时间为t=colors0[i]+colors1[j]-colors1[i]+colors2[-1]-colors2[j] 转化一下变成t=colors0[i]-colors1[i]+colors1[j]-colors2[j]+colors2[-1],也就是说因为第一个切点i肯定在第二个切点j的前面，所以我们只需要根据第二个切点j进行遍历，计算colors0[i]-colors1[i]的最小值（i<=j),最后算出的t取最小

    colors0=[cost0,cost1,cost2][color0]
    colors1=[cost0,cost1,cost2][color1]
    colors2=[cost0,cost1,cost2][color2]
    min_pre=colors0[1]-colors1[1]#当第二个切点在第一个元素后面，显然第一个切点有且只有一种情况，也在第一个元素后面（至于第一个元素前面的可能性，我写的切点全是在元素的后面，至于第一个切点在第一个元素前面本质上就是只用两种颜色，和在最后一个元素后面是一样的）
    t=min_pre+colors1[1]-colors2[1]+colors2[-1]#计算第二个切点在第一个元素后面的最小时间，因为i，j只有一种可能所以直接算即可
    for j in range(1,n):
        min_pre=min(colors0[j+1]-colors1[j+1],min_pre)#随着第二个切点j后移，只需要取第二个切点在j-1处和j的最小值
        t=min(t,min_pre+colors1[j+1]-colors2[j+1]+colors2[-1])#时间也是一样的
    return t

time=[]
for order in [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]:
    time.append(fun(*order))
print(min(time))
#本方法对于6种排列分别求最短的时间，只用循环一次，时间复杂度为O(n),感觉比排行上的更简单但是运行时间1725ms，不知道为什么
发表于 2025-06-24 17:54:54 回复(0)
提交观点

问题信息

动态规划
难度：
2条回答 508浏览

热门推荐

相关试题

气球谜题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号