Codeforces Round 913 (Div.3) C. Removal of Unattractive Pairs

[Woodyiiiiiii]

Codeforces Round 913 (Div.3) C. Removal of Unattractive Pairs

Codeforces Round 913 (Div.3) C. Removal of Unattractive Pairs

这道题显然是贪心，但我没想到怎么贪心，一直在思考各种情况。

不如直接想到最后留下什么，最佳情况下为0，最多剩下出现次数超过一半的元素，所以根据数组大小奇偶性判断是否有超过一半次数出现的元素即可。

为什么呢？最优的方式应该是在字符串消除的过程中，总是先消除最多出现次数的字符。

import java.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * Codeforces/Atcoder template
 */
public class Main {

    static final Reader RR = new Reader(System.in);
    static final PrintWriter PP = new PrintWriter(System.out, true);

    public static void main(String[] args) throws IOException {
        int T = RR.nextInt();
        while (T -- > 0) {
            solve();
        }
//        solve();
    }

    private static void solve() throws IOException {
        int n = RR.nextInt();
        String s = RR.next();
        Map<Character, Integer> cntMap = new HashMap<>();
        int maxCnt = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            cntMap.put(c, cntMap.getOrDefault(c, 0) + 1);
            maxCnt = Math.max(maxCnt, cntMap.get(c));
        }
        if (maxCnt > n / 2) {
            PP.println(maxCnt - n + maxCnt);
        } else {
            if (n % 2 == 0) {
                PP.println(0);
            } else {
                PP.println(1);
            }
        }
        }


    /**
     * Fast I/O
     */
    static class Reader {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public Reader(InputStream inputStream) {
            this.reader = new BufferedReader(new InputStreamReader(inputStream), 65536);
            this.tokenizer = new StringTokenizer("");
        }

        public String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // long
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

    }

}