P1653. 压缩贴纸题解

1. 题意理解

你会得到一段文本，需通过断行排版使贴纸面积最小。贴纸面积公式为：

$$\text{面积} = (\text{每行最大宽度} + 2) \times (\text{行数} + 2) $$

其中规则：

• 每行单词用单个空格分隔，标点（$, . ? !$）紧跟单词（如$"price."$视为长度6的单词）。
• 贴纸有1字符边距，因此行宽和行数需各加2。

2. 思路分析

核心矛盾

行宽越大，行数可能越少；但行宽过大会导致“空间浪费”（边距固定为2，行宽越大，面积的宽度项增长越快）。需枚举合理行宽范围，计算对应面积，取最小值。

关键观察

• 行宽下界：必须≥最长单词长度（否则该行无法容纳该单词）。
• 行宽上界：无需遍历到总长度（所有单词一行），可从总长度的一半开始枚举（实验表明，最优行宽通常接近总长度的中间范围，减少无效枚举）。

3. 具体实现步骤

步骤一：文本预处理（分割单词+合并标点）

• 用 $cin >> str$ 读取文本（自动跳过空格和换行，分割为单词/标点）。
• 若读取到标点（$, . ? !$），则将其长度合并到前一个单词（如$"elephants!"$长度为9）；否则记录单词长度到数组 $s$。

步骤二：计算总长度（辅助确定行宽范围）

总长度 = 所有单词长度之和 + 空格数（空格数 = 单词数 - 1）。

步骤三：确定行宽枚举范围

• 下界 $end$：$max\_element(s.begin(), s.end())$（最长单词长度）。
• 上界 $start$：从总长度的一半开始（遍历到 $end$ 即可，无需更大值）。

步骤四：枚举行宽，计算最小面积

对每个行宽 $w$（从 $start$ 到 $end$）：

• 调用 $calc(w, s)$ 模拟断行：逐词加入当前行，超过 $w$ 则换行，统计行数。
• 计算面积 $(w+2) \times (行数+2)$，更新全局最小值。

4. 复杂度分析

• 时间复杂度：

  • 文本预处理：$O(N)$（$N$ 为单词数）。
  • 行宽枚举：最多遍历 $O(\text{总长度}/2 - \text{最长单词长度})$ 次（通常 ≤ 500），每次调用 $calc$ 需 $O(N)$ 时间。
    总复杂度：$O(N \times M)$（$M$ 为行宽枚举次数，实际很小）。

• 空间复杂度：
  存储单词长度的数组 $s$ 占 $O(N)$ 空间，其余变量为常数级。

代码实现（附关键逻辑注释）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 计算行宽$w$对应的贴纸面积
int calc(int $w$, vector<int>& $s$) {
    int $curr\_width$ = 0; // 当前行已用宽度（含空格）
    int $rows$ = 0;       // 行数
    for (int $len$ : $s$) {
        if ($curr\_width$ + $len$ > $w$) { // 当前单词无法放入当前行
            $rows$++;
            $curr\_width$ = $len$ + 1;   // 新行：单词+空格（后续可能加更多单词）
        } else {
            $curr\_width$ += $len$ + 1;  // 放入当前行：单词+空格
        }
    }
    if ($curr\_width$ > 0) $rows$++; // 处理最后一行
    return ($w$ + 2) * ($rows$ + 2); // 加边距
}

int main() {
    vector<int> $s$; // 存储单词（含标点）的长度
    string $str$;

    // 步骤一：文本预处理
    while ($cin >> $str$) {
        if ($str$ == "," || $str$ == "." || $str$ == "?" || $str$ == "!") {
            $s$.back()++; // 标点合并到前一个单词
        } else {
            $s$.push_back($str$.size()); // 记录单词长度
        }
    }

    // 步骤二：计算总长度（辅助确定行宽范围）
    int $total\_len$ = $s$.size() - 1; // 空格数
    for (int $len$ : $s$) $total\_len$ += $len$;

    // 初始最小面积：所有单词一行的情况
    int $min\_area$ = ($total\_len$ + 2) * 3;

    // 步骤三：确定行宽枚举范围
    int $end$ = *max_element($s$.begin(), $s$.end()); // 下界：最长单词长度
    int $start$ = 0;
    for (int $len$ : $s$) {
        $start$ += $len$ + 1;
        if ($start$ >= $total\_len$ / 2) break; // 上界：总长度的一半附近
    }

    // 步骤四：枚举行宽，更新最小面积
    for (int $w$ = $start$; $w$ >= $end$; $w$--) {
        $min\_area$ = min($min\_area$, calc($w$, $s$));
    }

    cout << $min\_area$ << endl;
    return 0;
}

关键细节说明

1. 标点处理：通过 $s.back()$++ 将标点长度合并到前一个单词，保证排版时标点紧跟单词。
2. 行宽枚举优化：从总长度的一半开始反向遍历（而非从小到大），更早遇到接近最优的行宽（实验性优化，不影响正确性）。
3. 边距计算：公式中 +$2$ 对应贴纸的上下/左右边距，需严格遵循题意。

通过以上步骤，算法在合理时间内找到最优解，同时兼顾代码简洁性与效率。