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

解题思路:

贪心，先排升序，先买最大两个将可以免费的机会用队列存放，后续判断数量低于免费的就直接免费掉

二分查询加标记
注意事项:

注意空指针，开long

参考代码:

import java.util.*;
  
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n + 1];
        for(int i = 1; i <= n; i++){
            a[i] = scan.nextInt();
        }
        Arrays.sort(a); // 升序排序
        Queue queue = new LinkedList<>(); // 存放免费机会
        long res = 0;
        while (n > 0){
            while (!queue.isEmpty() && n > 0){   
                if(queue.peek() >= a[n]){ // 取出最大免费机会比较可以免费则指针向后并删除当前免费机会
                    queue.poll();
                    n--;
                }else {
                    break;  // 否则退出
                }
            }
            if(n > 0) {
                res += a[n]; 
                n--;
            }
            while (!queue.isEmpty() && n > 0){   
                if(queue.peek() >= a[n]){ // 取出最大免费机会比较可以免费则指针向后并删除当前免费机会
                    queue.poll();
                    n--;
                }else {
                    break;  // 否则退出
                }
            }
            if(n > 0) { // 防止越界,并取买的两个数中最小的价值的一半添加到免费机会
                res += a[n];
                queue.offer(a[n] / 2.0);
                n--;
            }
        }
        System.out.println(res);
    }
}

import java.util.*;    
    
    public class Main {    
        public static void main(String[] args) {    
            Scanner scan = new Scanner(System.in);    
            int n = scan.nextInt();    
            int[] a = new int[n + 1];    
            for(int i = 1; i <= n; i++){    
                a[i] = scan.nextInt();    
            }    
            Arrays.sort(a); // 升序排序    
            boolean[] flag = new boolean[n + 1];    
            int p;    
            long res = 0;    
            int cnt = 0;    
            while (n > 0){    
                if(flag[n]) {    
                    n--;    
                    continue;    
                }    
                cnt++;    
                res += a[n];    
                flag[n] = true;    
                if (cnt % 2 == 0) {    
                    p = a[n] / 2;    
                    binarySearch(a, flag, p);    
                }    
                n--;    
            }    
            System.out.println(res);    
        }    
        public static void binarySearch(int[] a, boolean[] flag, int p){    
            int l = 1;    
            int r = a.length;    
            int mid = (l + r) / 2;    
            while(l <= r){    
                mid = (l + r) / 2;    
                if(a[mid] > p || flag[mid]){    
                    r = mid - 1;    
                }else if(a[mid] < p ){    
                    l = mid + 1;    
                } else {    
                    break;    
                }    
            }    
            while(mid > 0){    
                if(flag[mid] || a[mid] > p){    
                    mid--;    
                }else{    
                    flag[mid] = true;    
                    return;    
                }    
            }    
        }    
    }