最小化二进制分箱行垂直列和的高效算法求解

理论最优下界 #

首先明确均匀分布的理论最优值：
所有行的1的总数量为 S = sum(k_i)，其中k_i为第i行的1的个数，那么每列的列和最优情况下只能是 floor(S/m) 或者 ceil(S/m)，不可能出现更小的最大列和，也不可能比这个分布更均匀。

确定性非迭代构造算法 #

这个方案属于纯数学构造，完全不需要迭代调整，支持百亿级行规模的流式处理，内存占用仅为O(1)，具体步骤如下：

1. 全局参数初始化：不需要提前计算所有行的k_i，流式处理时只需要维护一个前缀和模值 offset = 0
2. 单行1的位置计算：对于任意一行i，已知它需要放k_i个1：
   • 该行1的起始位置为 offset
   • 依次取位置 offset, offset+1, ..., offset + k_i -1，所有位置对m取模，就是该行所有1的位置
   • 更新offset = (offset + k_i) % m

如果需要支持随机访问任意第i行的1的位置，只需要提前预处理所有k_i的前缀和数组prefix_sum，其中prefix_sum[i]是前i行的k的总和，那么第i行的起始位置为prefix_sum[i] % m，不需要逐行计算即可直接得到任意行的1的位置。

示例验证 #

用你给出的4行10列的例子验证：
各行k值为：6,7,4,5，m=10

• 初始offset=0
• 第1行：起始位置0，取6个位置0-5，offset更新为(0+6)%10=6，行值为1 1 1 1 1 1 0 0 0 0
• 第2行：起始位置6，取7个位置6,7,8,9,0,1,2，offset更新为(6+7)%10=3，行值为1 1 1 0 0 0 1 1 1 1
• 第3行：起始位置3，取4个位置3,4,5,6，offset更新为(3+4)%10=7，行值为0 0 0 1 1 1 1 0 0 0
• 第4行：起始位置7，取5个位置7,8,9,0,1，offset更新为(7+5)%10=2，行值为1 1 0 0 0 0 0 1 1 1

最终计算列和为 3 3 2 2 2 2 2 2 2 2，和你给出的最优结果完全一致，达到了理论最优的均匀性。

方案优势 #

• 完全无迭代：所有位置都是纯公式计算，没有任何循环调整步骤
• 超大规模适配：流式处理时仅需维护一个offset变量，支持百万、十亿级行处理，内存占用可以忽略不计
• 支持随机访问：预处理前缀和后可以直接查询任意行的1的位置，不需要处理前面的所有行
• 最优性保证：最终列和最大差值不会超过1，达到理论上的最优均匀效果

内容的提问来源于stack exchange，提问作者kstisser