Codeforces - 1107C. Brutality

Question

题目

给你 n、k ，然后 n 个数( arr[i]) 以及长度为 n 的字符串( str[i] )，每次你可以拿走某个位置 i 上的字符，得到的价值是 arr[i] ，但是你在一段连续的相同的字符序列中，不能拿超过 k 个字符串(注意，不是连续的 k 个)。问你可以拿到的最大价值。

解析

一开始没有读懂题目，即: 在一段连续的相同的字符序列中，不能拿超过 k 个字符串，还以为是总共不能超过 k 个字符串，于是用 map + 堆 写了，那时还纳闷第一个样例不对，后来才看懂题目的意思。

• 遍历字符串，每次去找相同连续相同的字符序列；
• 然后对这一段字符序列对应的值排序，取最大的 k 个即可（不够的话就取所有的)；

一开始错误的代码:

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        int n = cin.nextInt();
        int k = cin.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = cin.nextInt();
        String str = cin.next();

        HashMap<Character, PriorityQueue<Integer>> counts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            PriorityQueue<Integer> tmpQ = counts.getOrDefault(c, new PriorityQueue<>());
            if (tmpQ.size() >= k) {
                if (arr[i] > tmpQ.peek()) {
                    tmpQ.poll();
                    tmpQ.add(arr[i]);
                }
            } else {
                tmpQ.add(arr[i]);
            }
            counts.put(c, tmpQ);
        }
        int res = 0;
        for(PriorityQueue<Integer>q : counts.values()){
            while(!q.isEmpty())
                res += q.poll();
        }
        System.out.println(res);
    }
}

最后修改的正取的代码:

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        int n = cin.nextInt();
        int k = cin.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = cin.nextInt();
        String str = cin.next();
        long res = 0;
        for (int i = 0; i < n; ) {
            char c = str.charAt(i);
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < n && str.charAt(j) == c) {
                tmp.add(arr[j]);
                j++;
            }
            Collections.sort(tmp, Collections.reverseOrder());
            for (int p = 0; p < Math.min(tmp.size(), k); p++) res += tmp.get(p);
            i = j;
        }
        System.out.println(res);
    }
}

题目链接

https://codeforces.com/problemset/problem/1107/C