我有 n 个不同长度的字符串 s₁, s₂, ..., s_n 我想在 c 列中显示在终端上。终端的宽度为 m 个字符。每列 i 具有一定的宽度 w_i，该宽度等于该列中最长条目的宽度。每对列之间都有一定的空间s。包括间距在内的所有列的总宽度不能大于终端的宽度(w₁ + w₂ + ... + w_c + (c - 1) ·s ≤ m)。每列应包含 ⌈n/c⌉ 字符串，除非 n 不能被 c 整除，在这种情况下，最后几列应缩短一个条目或仅最后一列更短，具体取决于字符串是横向排列还是向下排列。

是否有一个有效的(例如O(n·w) where w = max(w₁, w₂, ..., w_n)) 算法来找出我可以放入 c 列，如果...

• 字符串是跨行排列的

  string1 string2  string3 string4
  string5 string6  string7 string8
  string9 string10
  

• 字符串向下排列

  string1 string4 string7 string10
  string2 string5 string8
  string3 string6 string9
  

?

后来的发现

我发现 s 并不重要。 s > 0 的每个问题实例都可以通过用 s 个字符扩展每个字符串并扩展来转换为 s = 0 的实例终端的宽度由 s 个字符来补偿屏幕末尾额外的 s 个字符。

最佳答案

不幸的是，我认为最快的算法是 O(n^2)。这是因为您可以确定是否可以在列表的单次传递中对 c 列进行配置，但您不知道更改 c 的程度，所以基本上您只需要为它尝试不同的值。最多你的算法会这样做 n 次。

这是我如何做的伪代码

for c = n.size, c > 0, c --
  remainingDist = m - c*s
  for i = 1, i <= c, i ++ 
    columnWidth = 0
    for j = i, j <= n.size; j += c
      columnWidth = max(n[j], columnWidth)
    end
    remainingDist -= columnWidth
  end
  if remainingDist >= 0
    success
    columns = c
    break
  end
end

您可以通过首先计算项目的平均大小并从中计算出“理想”的列数来跳转到循环的中途。

https://stackoverflow.com/questions/24411759/