如何有效地找到一定宽度的字符串的理想列数？

Question

我有Ñ的不同长度的字符串小号₁,S ₂,...,S _Ñ我要显示在终端上Ç列.终端的宽度为m个字符.每列i具有一定宽度w _i,其等于该列中最长条目的宽度.每对列之间有空间的一定量的小号.包括空间之间的所有列的总宽度不能大于端子的宽度(w ₁ + w ₂ + ... + w _c +(c-1)·s≤m).每列应包含⌈n / c⌉字符串,除非n不能由c均匀分割,在这种情况下,最后几列应缩短一个条目,或者只有最后一列应短,取决于字符串是否排列横向或向下.

是否存在有效的(例如O(n·w),其中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 = 0,通过扩大每个字符串小号通过字符,并且还扩大了端子的宽度小号字符,以补偿额外的小号在屏幕的结束字符.

Answer 1

不幸的是，我认为最快的算法是 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

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