题目分析

有 $N$ 门课程，$M$ 周时间。每周每门课有一次课，对于每节课可以选择：

• 去上课：获得 $A_i$ 熟练度
• 翘课自学：获得 $B_i$ 熟练度（可以选任意课程自学）

目标：让所有课程熟练度的最小值最大化。

核心思路

二分答案框架

使用二分答案确定可能的最大最小值 $x$，检查是否能让所有课程的熟练度都至少达到 $x$。

int l = 1, r = 1e18 + 1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid))
        l = mid + 1, ans = mid;
    else
        r = mid - 1;
}

可行性检查函数 check(x)

关键思想：对于每门课程 $i$，计算达到熟练度 $x$ 所需的最少周数。

情况分析

对于课程 $i$：

1. 如果 $max(A_i, B_i) \times M \geq x$

   • 主要使用效率更高的方式（上课或自学）
   • 需要周数：$\lceil \frac{x}{max(A_i, B_i)} \rceil$

2. 否则（即 $max(A_i, B_i) \times M < x$）

   • 先用 $M$ 周获得 $max(A_i, B_i) \times M$ 熟练度
   • 剩余熟练度 $x - max(A_i, B_i) \times M$ 必须通过另一种方式获得
   • 需要额外周数：$\lceil \frac{x - max(A_i, B_i) \times M}{min(A_i, B_i)} \rceil$

资源分配

• 总可用周数：$N \times M$（每周 $N$ 节课，共 $M$ 周）
• 每门课程消耗周数累加，检查是否超过总资源

代码详解

可行性检查函数

int check(int x) {
    int k = n * m;  // 总可用节数

    for (int i = 1; i <= n; i++) {
        int s = max(a[i], b[i]);  // 选择更高效的方式
        
        if (s * m >= x) {
            // 主要使用高效方式即可达到目标
            k -= (x + s - 1) / s;  // 向上取整
        } else {
            // 需要结合两种方式
            k -= m;  // 先用m周高效方式
            k -= (x - s * m + b[i] - 1) / b[i];  // 剩余用另一种方式
        }
        
        if (k < 0) return 0;  // 资源不足
    }
    
    return k >= 0;  // 资源足够
}

注意：这里使用 $b[i]$ 而不是 $min(a[i], b[i])$，因为：

• 当 $s = max(a[i], b[i])$ 时，另一种方式就是 $min(a[i], b[i])$
• 但代码中统一用 $b[i]$ 处理，这在 $a[i] \geq b[i]$ 时正确，在 $a[i] < b[i]$ 时也正确（因为此时 $s = b[i]$）

边界情况处理

• 向上取整技巧：(x + s - 1) / s 等价于 $\lceil \frac{x}{s} \rceil$
• 大数处理：使用 long long 避免溢出
• 答案范围：$[1, 10^{18}+1]$ 覆盖所有可能情况

算法正确性

单调性

如果 $x$ 可行，那么所有小于 $x$ 的值都可行；如果 $x$ 不可行，那么所有大于 $x$ 的值都不可行。

最优性

二分找到的是最大的可行 $x$ 值。

复杂度分析

• 时间复杂度：$O(N \log (\text{答案范围}))$

  • 每次 check 函数 $O(N)$
  • 二分次数 $O(\log (10^{18})) \approx 60$
  • 总复杂度 $O(60N)$，对于 $N \leq 3 \times 10^5$ 可接受

• 空间复杂度：$O(N)$ 存储数组

样例验证

样例1

n=3, m=3
A = [19,4,5], B = [2,6,2]

输出：18

验证过程：二分找到最大 $x=18$ 使得所有课程熟练度都能达到 18。

样例2

n=2, m=1  
A = [9,7], B = [2,6]

输出：7

由于只有1周，最优策略是让两门课分别达到 9 和 7，最小值是 7。

总结

本题是典型的二分答案 + 贪心验证问题：

1. 二分答案确定可能的最大最小值
2. 贪心验证为每门课程选择最优学习策略
3. 资源统计确保总周数不超过限制

这种解法高效且易于实现，能够处理大规模数据。