蓝桥杯2023年第十四届省赛真题-买二赠一 (优先队列）

解题思路:  两个最小堆

参考代码:

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


public class Main {

    static void Solve() throws IOException {
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        Queue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            q.offer(a[i]);
        }
        Queue<Integer> p = new PriorityQueue<>((o1, o2) -> o2 - o1);
        long cnt = 0;
        while (!q.isEmpty()) {
            while (!p.isEmpty() && !q.isEmpty() &&  p.peek() >= q.peek()) {
                p.poll();
                int o = q.poll();
                //out.println("免费的是 :" + o);
            }
            if (!q.isEmpty()) {
                int v = q.poll();
                cnt += v;
                //out.println("买入大的 :" + v);
            }
            if (!q.isEmpty()) {
                while (!p.isEmpty() && !q.isEmpty() &&  p.peek() >= q.peek()) {
                    p.poll();
                    int o = q.poll();
                    //out.println("免费的是 :" + o);
                }
                if (!q.isEmpty()){
                    int t = q.poll();
                    cnt += t;
                    //out.println("买入小的 :" + t);
                    p.add(t / 2);
                    //out.println("买入小的p添加一半后是 :" + (t / 2));
                }
            }
        }
        out.println(cnt);
    }


    /*

     */

    public static void main(String[] args) throws IOException {
        int t = 1;
//        int t = sc.nextInt();
        while (t-- > 0) Solve();
        out.flush();
        out.close();
        br.close();
    }


    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Input sc = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}