1. 定理简介
例题
Gale-Ryser 定理是图论中的一个经典定理，用于判定：给定两组度数要求，是否存在一个满足这些要求的“简单二分图”（即左右两边的顶点之间最多只能连一条边）。
在本题中，问题被完美映射为构建简单二分图：
-
左部节点：\(M\) 本书，节点度数为 \(R_j\)（每本书需要被看 \(R_j\) 次）。
-
右部节点：\(N\) 天，节点最大度数为 \(L_i\)（每天最多看 \(L_i\) 本书）。
-
边的限制：同一天同一本书只能看一次（简单二分图没有重边）。
2. 核心概念：共轭序列 (Conjugate Sequence)
为了应用定理，我们需要理解如何将容量序列转化。
假设每天的容量序列 \(L\) 降序排列后画成砖块（Ferrers 图），共轭序列 \(L^*\) 就是将这个图形“竖着看”（按列统计）得到的序列。
-
物理意义：\(L^*_k\) 表示 “容量至少为 \(k\) 的天数总共有多少天”。
-
代码实现：对 \(L\) 升序排序后，
L.end() - lower_bound(L.begin(), L.end(), k)就是在以 \(O(\log N)\) 的极快速度求出 \(L^*_k\) 的值。
3. 判定条件 (Gale-Ryser Condition)
将需求序列 \(R\) 降序排列（优先满足需求最大的书）。定理指出，存在合法排班方案的充要条件是：
对于任意的 \(k \in [1, M]\)，前缀和均满足以下不等式：
(注：如果要求二分图的度数刚好严格等于 \(L\)，则最后还需要加上总和相等 \(\sum R = \sum L\) 的条件。本题天数容量是上限，所以只需满足不等式即可。)
4. 底层逻辑：为什么比较前缀和？
假设我们要强行满足需求量最大的前 \(k\) 本书。
对于这 \(k\) 本书，系统能提供的理论最大合法容量是多少？
-
如果某天容量充足（\(L_i \ge k\)），因为一天一本书只能看一次，这天最多只能给这 \(k\) 本书提供 \(k\) 个名额。
-
如果某天容量不足（\(L_i < k\)），这天即使全用来排这 \(k\) 本书，也只能提供 \(L_i\) 个名额。
将所有天数能提供的最大名额加起来 \(\sum \min(L_i, k)\)，在数学上刚好等于共轭序列 \(L^*\) 的前 \(k\) 项之和。
如果需求总和超出了这个系统能提供的物理极限（即 \(\sum R > \sum L^*\)），则必然无解。
5. 算法模板抽象
解决此类“判断多对多容量与需求匹配”的问题，只需三步，时间复杂度 \(O(M \log N + M \log M)\)：
// 1. 容量 L 升序排序 (为了方便二分查找)
sort(L.begin(), L.end());// 2. 需求 R 降序排序 (贪心优先满足大需求)
sort(R.begin(), R.end(), greater<int>());long long sum_R = 0; // 需求前缀和
long long sum_C = 0; // 容量共轭序列前缀和// 3. 逐项验证前缀和
for (int k = 0; k < M; k++) {sum_R += R[k];// 巧妙求出共轭序列的第 k+1 项：容量 >= k+1 的天数long long current_L_star = L.end() - lower_bound(L.begin(), L.end(), k + 1);sum_C += current_L_star;// 一旦需求超过最大理论容量，立刻判定无解if (sum_R > sum_C) {return false; }
}
return true; // 所有前缀均满足，必定有解