问题分析

我们有 $N$ 个人分享一个长度为 $L$ 的馕，馕被分成 $L$ 段，每段 1 厘米，有不同的口味。第 $i$ 个人对第 $j$ 种口味的快乐度系数是 $V_{i,j}$。

我们需要将馕切成 $N$ 段，分配给 $N$ 个人，使得每个人获得的快乐度不少于他们独享整个馕的 $\frac{1}{N}$。

---

关键思路

1. 快乐度计算

设第 $i$ 个人吃整个馕的总快乐度为： $S_i = \sum_{j=1}^L V_{i,j}$ 公平性要求：第 $i$ 个人分配的快乐度 $\ge \frac{S_i}{N}$。

2. 连续分配的性质

由于馕是连续的，我们可以将问题转化为在 $[0, L]$ 区间上找 $N-1$ 个分割点。

对于第 $i$ 个人，如果我们知道他要吃区间 $[a, b]$，那么他的快乐度是：

$$\text{joy}_i(a,b) = \sum_{j=\lceil a \rceil}^{\lfloor b \rfloor - 1} V_{i,j} + V_{i,\lfloor b \rfloor} \cdot (b - \lfloor b \rfloor) + V_{i,\lceil a \rceil} \cdot (\lceil a \rceil - a) $$

3. 核心观察：相对进度

定义第 $i$ 个人在位置 $x$ 的累积快乐度比例：

$$f_i(x) = 第 i 个人在区间 [0, x] 上的快乐度/s_i$$

即 $f_i(x)$ 表示如果第 $i$ 个人吃到位置 $x$，他获得了自己总快乐度的多大比例。

关键性质：对于任意 $t \in [0,1]$，存在位置 $x$ 使得 $f_i(x) = t$（由于连续性）。

4. 构造算法

我们可以按以下步骤构造解：

计算总快乐度：对于每个人 $i$，计算 $S_i = \sum_{j=1}^L V_{i,j}$

确定分割点：

设当前剩余人员集合为 $P$

对于 $k = 1$ 到 $N-1$：

找到最小的 $x_k$，使得存在某人 $p \in P$ 满足 $f_p(x_k) = \frac{k}{N}$

选择满足条件的 $p$ 中 $f_p(x_k)$ 增长最慢的（即最"贪心"的人）

将 $x_k$ 作为第 $k$ 个分割点，将 $p$ 分配到这个区间

从 $P$ 中移除 $p$

分配最后一个人：将最后剩余的人分配给最后一个区间 $[x_{N-1}, L]$

5. 算法正确性

正确性证明：

对于第 $k$ 个区间 $[x_{k-1}, x_k]$（设 $x_0=0, x_N=L$），分配给的人 $p$ 满足：

$$f_p(x_k)-f_p(x_k-1) \le \frac{1}{N}$$

因为 $f_p(x_k) = \frac{k}{N}$，而 $f_p(x_{k-1}) \le \frac{k-1}{N}$（由构造保证）

因此，第 $p$ 个人获得的快乐度比例至少为 $\frac{1}{N}$，即快乐度 $\ge \frac{S_p}{N}$

对于最后一个人 $q$，由于 $f_q(L) = 1$，且 $f_q(x_{N-1}) \le \frac{N-1}{N}$，所以他在最后一个区间的快乐度比例 $\ge \frac{1}{N}$

6. 数值实现

由于题目要求输出分数形式 $\frac{A_i}{B_i}$，我们可以：

将每个位置 $x$ 表示为有理数

对于 $f_i(x) = t$，我们需要解：

$$\frac{\sum_{j=1}^{\lfloor x \rfloor} V_{i,j} + V_{i,\lceil x \rceil} \cdot (x - \lfloor x \rfloor)}{s_i} =t $$

设 $x = m + \alpha$，其中 $m = \lfloor x \rfloor$，$0 \le \alpha < 1$，则：

$$α=\frac{\alpha = \frac{t \cdot S_i - \sum_{j=1}^{m} V_{i,j}}{V_{i,m+1}}}{v_{i,m}+1} $$

因此 $x = m + \alpha$ 可以表示为有理数。

---

算法步骤

详细算法：

计算 $S_i = \sum_{j=1}^L V_{i,j}$ 对于 $i=1,\dots,N$

初始化剩余人员集合 $P = {1,\dots,N}$，分割点列表 $X = []$，分配方案 $assign = []$

对于 $k = 1$ 到 $N-1$：

对于每个 $p \in P$，计算最小的 $x_p$ 使得 $f_p(x_p) = \frac{k}{N}$

选择 $x^* = \min_{p \in P} x_p$，对应的 $p^* = \arg\min_{p \in P} x_p$

将 x^ 加入 $X$，将 p^ 加入 $assign$，从 $P$ 中移除 $p^*$

将剩余的唯一人员加入 $assign$

输出分割点 $X$（表示为分数）和分配方案 $assign$

---

复杂度分析

计算 $S_i$：$O(NL)$

对于每个 $k$，计算所有剩余人员的 $x_p$：$O(NL)$

总复杂度：$O(N^2L)$，对于 $N,L \le 2000$ 可接受

---

示例验证

以样例1为例：

$S_1 = 20$, $S_2 = 14$

$k=1$：$f_1(x)=0.5$ 时 $x=2.8$，$f_2(x)=0.5$ 时 $x≈2.57$，选择较小的 $x=2.8$

输出 $\frac{14}{5}=2.8$，分配 $P_1=2$，$P_2=1$

---

总结

这道题的核心在于利用连续性保证公平分配的存在性，通过贪心选择"最急需"的人来确保所有人都能满足 $\frac{1}{N}$ 的快乐度要求。算法构造性地证明了解的存在，并给出了有效的构造方法。