首页 > 试题广场 >

气球谜题

[编程题]气球谜题
  • 热度指数：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 。
算法知识视频讲解
添加回答
Java
清浅QAQ头像 清浅QAQ
6种排列比较但是过不了第一个用例，不知道错在哪里
import java.util.*;

public class Main {
    static int[] spend;
    static int[] colorCount = new int[3]; // 0: red, 1: yellow, 2: blue

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        spend = new int[n];
        for (int i = 0; i < n; i++) {
            spend[i] = in.nextInt();
        }

        // 统计每种颜色的数量
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            if (c == '0') colorCount[0]++;
            else if (c == '1') colorCount[1]++;
            else colorCount[2]++;
        }

        int minTime = Integer.MAX_VALUE;
        // 6 种可能的排列方式
        minTime = Math.min(minTime, calculateTime(str, 0, 1, 2));
        minTime = Math.min(minTime, calculateTime(str, 0, 2, 1));
        minTime = Math.min(minTime, calculateTime(str, 1, 0, 2));
        minTime = Math.min(minTime, calculateTime(str, 1, 2, 0));
        minTime = Math.min(minTime, calculateTime(str, 2, 0, 1));
        minTime = Math.min(minTime, calculateTime(str, 2, 1, 0));

        System.out.println(minTime);
    }

    public static int calculateTime(String str, int first, int second, int third) {
        int time = 0;
        int r1 = colorCount[first];
        int r2 = colorCount[second];
        int r3 = colorCount[third];

        // 第一部分：检查前 r1 个位置是否应该是 first 颜色
        for (int i = 0; i < r1; i++) {
            char c = str.charAt(i);
            if (c - '0' != first) {
                time += spend[i];
            }
        }

        // 第二部分：检查接下来的 r2 个位置是否应该是 second 颜色
        for (int i = r1; i < r1 + r2; i++) {
            char c = str.charAt(i);
            if (c - '0' != second) {
                time += spend[i];
            }
        }

        // 第三部分：检查剩下的位置是否应该是 third 颜色
        for (int i = r1 + r2; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c - '0' != third) {
                time += spend[i];
            }
        }

        return time;
    }
}

发表于 2025-09-08 17:02:39 回复(0)
Java
牛客279643016号头像 牛客279643016号
我用excel算了这个用例，答案就是2572，程序判断有问题，我的代码参考如下
100
2112211000202002110122220012110100110022010102200201202122022210001002120112010210021012001212010210
49 77 40 28 38 55 17 53 33 68 57 7 56 78 77 68 99 82 41 26 64 69 1 98 98 63 15 13 95 23 71 6 57 4 10 10 44 11 84 10 59 62 94 49 7 46 37 87 79 6 85 91 42 42 34 94 51 89 98 29 12 64 97 23 20 97 80 17 38 76 83 65 40 41 55 3 16 56 13 11 74 31 24 9 76 4 51 99 76 25 93 39 37 74 23 46 19 54 57 14

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int total = Integer.valueOf(in.nextLine());
        String str = in.nextLine();
        int[] weight = new int[total];
        for (int i = 0; i < total; i++) {
            weight[i] = in.nextInt();
        }
        if (str.matches("[0]+") || str.matches("[1]+") || str.matches("[2]+")) {
            System.out.println(0);
            return;
        }
        int result = -1;
        for (int i = 1; i < total; i++) {
            for (int j = i + 1; j < total; j++) {
                int result1 = dfs(str, 0, i, weight);
                int result2 = dfs(str, i, j, weight);
                int result3 = dfs(str, j, total, weight);
                int sum = result1 + result2 + result3;
                result = result == -1 ? sum : Math.min(result, sum);
            }
        }
        System.out.println(result);
    }

    static Map<String, Integer> map = new LinkedHashMap<>();

    public static int dfs(String input, int x, int y, int[] weight) {
        if (map.containsKey(x + ":" + y)) {
            return map.get(x + ":" + y);
        }
        int result0 = 0;
        int result1 = 0;
        int result2 = 0;
        for (int i = x; i < y; i++) {
            char ch = input.charAt(i);
            // 改成0
            if (ch != '0') {
                result0 += weight[i];
            }
            // 改成1
            if (ch != '1') {
                result1 += weight[i];
            }
            // 改成2
            if (ch != '2') {
                result2 += weight[i];
            }
        }
        int min = Math.min(Math.min(result0, result1), result2);
        map.put(x + ":" + y, min);
        return min;
    }

发表于 2025-03-21 22:11:59 回复(1)
提交观点

问题信息

动态规划
难度：
3条回答 507浏览

热门推荐

相关试题

气球谜题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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