用归纳法易证，每次将一个前缀分给一个人，如果需要的长度是最短的，则对于剩下的人一定有解。用每个人初始的分割点来划分可以避免分母过大。

时间复杂度：$O(N(N+L))$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, l;
    std::cin >> n >> l;
    std::vector<std::vector<int>> v(n, std::vector<int>(l));
    std::vector<std::vector<int>> s(n, std::vector<int>(l + 1));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < l; ++j) std::cin >> v[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < l; ++j) s[i][j + 1] = s[i][j] + v[i][j];
    std::vector<std::vector<std::pair<long long, int>>> r(n, std::vector<std::pair<long long, int>>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0, k = 0; j < n; ++j) {
            while (1ll * s[i][k + 1] * n <= 1ll * s[i][l] * j) ++k;
            int den = n * v[i][k];
            r[i][j] = std::make_pair(1ll * s[i][l] * j - 1ll * s[i][k] * n + 1ll * k * den, den);
        }
    }
    std::vector<bool> vis(n);
    std::vector<int> p(n);
    for (int i = 0; i < n - 1; ++i) {
        int u = -1;
        long long num = l * n;
        int den = n;
        for (int j = 0; j < n; ++j) {
            if (vis[j])
                continue;
            auto [x, y] = r[j][i + 1];
            if (x * (den / n) < num * (y / n)) {
                u = j;
                num = x;
                den = y;
            }
        }
        vis[u] = true;
        p[i] = u;
    }
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            p[n - 1] = i;
    for (int i = 1; i < n; ++i) std::cout << r[p[i - 1]][i].first << " " << r[p[i - 1]][i].second << "\n";
    for (int i = 0; i < n; ++i) std::cout << p[i] + 1 << " \n"[i == n - 1];
    return 0;
}