一、小红的口罩

‘

使用最小堆（PriorityQueue）模拟贪心

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long k = in.nextLong();   // 注意使用 long，防止溢出

        // 最小堆，存储当前所有口罩的不舒适度
        PriorityQueue<Long> heap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            long x = in.nextLong();
            heap.offer(x);
        }

        long sum = 0;   // 总不舒适度
        int days = 0;   // 天数

        while (true) {
            long cur = heap.poll();   // 取当前不舒适度最小的口罩

            if (sum + cur > k) {
                break;   // 超过阈值，无法使用
            }

            sum += cur;
            days++;
            heap.offer(cur * 2);   // 使用后翻倍，重新入堆
        }

        System.out.println(days);
    }
}

核心思路：贪心 + 最小堆

每天我们要选一个口罩来戴。显然，为了在总成本不超过 k 的前提下撑尽量多天数，每次应该选当前不舒适度最小的口罩。
因为这样做，今天付出的成本最小，剩下的“预算”就最多，从而可能获得更多天数。

翻倍机制意味着：一个口罩今天用了，明天它的成本就变大了，所以不能再无脑重复用同一个，它可能不再是明天最便宜的选择。因此我们需要动态维护所有口罩的当前成本，并且每次取出最小的。

这正好可以用最小堆（PriorityQueue） 来实现：堆顶永远是当前所有口罩中不舒适度最小的那个。

.1 数据结构：PriorityQueue<Long>

• Java 默认是最小堆，heap.poll() 返回并删除堆顶（最小值）。

• 为什么用 Long？因为口罩翻倍可能很快超过 int 范围（例如 a[i]=10^5，翻倍几次就超了），而 k 也可能很大，所以统一用 long 安全。

3.2 主循环的逻辑

• 每次循环，假设我们选择当前最便宜的口罩使用。

• 检查条件：sum + cur <= k 才允许用。

  • 如果成立：更新总成本、天数，然后把翻倍后的口罩放回堆。

  • 如果不成立：连最便宜的都不能用了，那其他口罩更贵，更不能用，所以直接退出循环。

二、春游

分析：

1. 如果n<=2，直接输出min(a,b)（因为可以租一条双人船或三人船，但三人船可能更便宜）。

2. 否则，如果3*a <= 2*b，意味着双人船人均成本更低（因为双人船人均a/2，三人船人均b/3，3*a <= 2*b等价于a/2 <= b/3）。所以优先用双人船。

   • ret = (n/2)*a

   • 如果n是奇数，剩一个人：
     方案1：多租一个双人船（但只坐一人）花费a，或者多租一个三人船花费b -> min(a,b)
     方案2：也可以考虑减少一条双人船（-a），然后租一条三人船（+b），即用b替代两个a？注意：剩一个人时，可以有两种思路：

     • 直接加一个船：min(a,b)

     • 或者退掉一条双人船（省a），然后改租一条三人船（花b），这样原来两个人加剩下一个人共三人坐一条三人船，总花费 ret - a + b
       取这两种的最小值。

3. 否则（即3a > 2b），三人船人均成本更低，优先用三人船。

   • ret = (n/3)*b

   • 余数情况：

     • 余1：剩一个人。
       方案1：加一个船 min(a,b)
       方案2：退掉一条三人船（-b），然后加两条双人船（+2*a），即用2a替代b来坐原来3人+剩余1人共4人？实际上逻辑是：少用一个三人船（省b），然后多租两个双人船（花2a），这样总花费 ret - b + 2*a

     • 余2：剩两个人。
       方案1：加一个船 min(a,b)
       方案2：退掉一条三人船（-b），然后加三条双人船（+3*a），即用3a替代b来坐原来3人+剩余2人共5人？类似。

   • 注意：还需要考虑余数为0直接输出。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long n = sc.nextLong();
            long a = sc.nextLong();
            long b = sc.nextLong();
            long ret = 0;

            if (n <= 2) {
                // 人数不超过2时，直接选最便宜的船（双人船或三人船）
                ret = Math.min(a, b);
            } else if (3 * a <= 2 * b) {
                // 双人船人均成本更低，优先用双人船
                ret = (n / 2) * a;
                if (n % 2 == 1) {
                    // 剩余1人：要么加一个船，要么退一条双人船换一条三人船
                    long opt1 = ret + Math.min(a, b);
                    long opt2 = ret - a + b;
                    ret = Math.min(opt1, opt2);
                }
            } else {
                // 三人船人均成本更低，优先用三人船
                ret = (n / 3) * b;
                long r = n % 3;
                if (r == 1) {
                    // 剩余1人：加一个船 或 退一条三人船换两条双人船
                    long opt1 = ret + Math.min(a, b);
                    long opt2 = ret - b + 2 * a;
                    ret = Math.min(opt1, opt2);
                } else if (r == 2) {
                    // 剩余2人：加一个船 或 退一条三人船换三条双人船
                    long opt1 = ret + Math.min(a, b);
                    long opt2 = ret - b + 3 * a;
                    ret = Math.min(opt1, opt2);
                }
            }
            System.out.println(ret);
        }
        sc.close();
    }
}