当前位置：首页 > article >正文

[蓝桥杯]图形排版

article 2025/6/6 6:41:27

图形排版

题目描述

小明需要在一篇文档中加入 NN 张图片，其中第 ii 张图片的宽度是 WiWi，高度是 HiHi。

假设纸张的宽度是 MM，小明使用的文档编辑工具会用以下方式对图片进行自动排版：

1. 该工具会按照图片顺序，在宽度 MM 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 M=10M=10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为 4。(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第 xx 张图片占用的版面)

0123456789

----------

111

111 333

11122333

2.如果当前行剩余宽度大于 0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张 4x9 的图片，由于剩余宽度是 2，这张图片会被压缩到 2x5，再被放入第一行的末尾。此时该行高度为 5：

0123456789

---------

111 44

111 33344

1112233344

3.如果当前行剩余宽度为 0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 NN 张图片的排版高度。例如再放入 11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为 11：

0123456789

----------

111 44

111 33344

1112233344

5555555555

66666

66666777

现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 NN 张图片中选择一张删除掉以降低总高度。他希望剩余 N−1N−1 张图片按原顺序的排版高度最低，你能求出最低高度是多少么？

输入描述

第一行包含两个整数 M,NM,N，分别表示纸张宽度和图片的数量。

接下来 NN 行，每行 2 个整数 Wi,HiWi,Hi，表示第 ii 个图大小为 Wi×HiWi×Hi。

其中,1≤N≤1051≤N≤105，1≤M,Wi,Hi≤1001≤M,Wi,Hi≤100。

输出描述

一个整数，表示在删除掉某一张图片之后，排版高度最少能是多少。

输入输出样例

示例

输入

输出

运行限制

最大运行时间：2s
最大运行内存: 256M

总通过次数: 1602 | 总提交次数: 2957 | 通过率: 54.2%

难度: 困难标签: 2017, 模拟, 省赛, 搜索

算法思路

本问题需要高效处理图片排版和删除优化，核心挑战在于：

排版规则复杂：涉及原始图片放置、缩放处理、行高计算
数据规模大：N ≤ 10⁵，需O(N)或O(N log N)解法
删除优化：需快速计算删除每张图片后的排版高度

采用双向预处理+模拟重新排版策略：

正向预处理：计算不删除时的行信息（起始位置、行高、下一行起点）
后缀数组预处理：g[i]表示从第i张图开始排版的总高度
枚举删除：对每个图片，重新排版所在行并拼接前后部分高度

算法演示

算法步骤

正向排版预处理
- 模拟整个序列排版，记录：
  - lines[]：每行起始下标
  - row_id[]：每张图片所在行号
  - nxt_line[]：每行结束后的下一行起点
  - line_height[]：每行高度
  - pre_total[]：前行累计高度
后缀数组g[i]计算
- 从后向前动态规划：
  - g[N+1] = 0
  - 对每个i从N到1：
    - 模拟从i开始排版一行
    - 计算行高和结束位置j
    - g[i] = 行高 + g[j]
枚举删除并计算
- 对每张图片k：
  - 定位所在行x和起始位置L0
  - 重新排版该行（跳过k）：
    - 遍历行内图片（跳过k）
    - 根据剩余空间缩放图片
    - 计算新行高和结束位置next_start
  - 总高度 = 前行高度 + 新行高 + g[next_start]
- 取所有删除方案的最小高度

代码实现（C++）

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;const int MAXN = 100010;
int M, N;
int W[MAXN], H[MAXN];
int lines[MAXN], row_id[MAXN], nxt_line[MAXN], line_height[MAXN];
long long pre_total[MAXN], g[MAXN];// 缩放高度计算（向上取整）
inline int calc_scaled_height(int w, int h, int space) {return (h * space + w - 1) / w;  // 整数运算避免浮点误差
}int main() {ios::sync_with_stdio(false);cin.tie(0);// 输入数据cin >> M >> N;for (int i = 1; i <= N; i++) {cin >> W[i] >> H[i];}// 正向排版预处理int row_count = 0;for (int i = 1; i <= N; ) {lines[++row_count] = i;  // 记录行起始int current_width = 0;int max_h = 0;int j = i;// 排版当前行while (j <= N) {if (current_width + W[j] <= M) {current_width += W[j];max_h = max(max_h, H[j]);row_id[j] = row_count;  // 记录图片所在行j++;} else {if (current_width < M) {int space = M - current_width;int scaled_h = calc_scaled_height(W[j], H[j], space);max_h = max(max_h, scaled_h);row_id[j] = row_count;j++;  // 缩放后放入，指向下一张current_width = M;  // 行满}break;}}line_height[row_count] = max_h;nxt_line[row_count] = j;  // 下一行起始i = j;  // 处理下一行}// 计算前行累计高度for (int i = 1; i <= row_count; i++) {pre_total[i] = pre_total[i - 1] + line_height[i];}// 后缀数组g[i]计算g[N + 1] = 0;for (int i = N; i >= 1; i--) {int current_width = 0;int max_h = 0;int j = i;// 从i开始排版一行while (j <= N) {if (current_width + W[j] <= M) {current_width += W[j];max_h = max(max_h, H[j]);j++;} else {if (current_width < M) {int space = M - current_width;int scaled_h = calc_scaled_height(W[j], H[j], space);max_h = max(max_h, scaled_h);j++;  // 缩放后放入}break;}}g[i] = max_h + g[j];  // 当前行高 + 后续高度}// 枚举删除每张图片long long ans = 1e18;for (int k = 1; k <= N; k++) {int x = row_id[k];       // k所在行号int L0 = lines[x];       // 行起始位置long long prefix = pre_total[x - 1];  // 前行总高度// 重新排版当前行（跳过k）int current_width = 0;int max_h = 0;int j = L0;while (j <= N) {if (j == k) {  // 跳过被删除图片j++;continue;}if (current_width + W[j] <= M) {current_width += W[j];max_h = max(max_h, H[j]);j++;} else {if (current_width < M) {int space = M - current_width;int scaled_h = calc_scaled_height(W[j], H[j], space);max_h = max(max_h, scaled_h);j++;  // 缩放后放入}break;}}// 总高度 = 前行高度 + 新行高 + 后续高度long long total_height = prefix + max_h + g[j];ans = min(ans, total_height);}cout << ans << endl;return 0;
}

代码解析

数据结构
- W[i], H[i]：存储图片宽高
- lines[]：记录每行起始图片下标
- row_id[i]：图片i所在行号
- g[i]：从第i张图开始排版的总高度
关键函数
- calc_scaled_height()：计算缩放高度（整数运算避免浮点误差）
- 正向排版：模拟自动排版过程，记录行信息
- 后缀计算：动态规划生成g[]数组，加速后续查询
删除优化
- 枚举删除每张图片时，仅重新排版其所在行
- 利用预处理的g[]数组快速获取后续排版高度
- 时间复杂度：O(100N)（每行最多处理100张图）

实例验证

输入样例：

处理过程：

原始排版：
- 行1：图片1(2×2) + 图片2(2×3) → 行高=3
- 行2：图片3(2×2) → 行高=2
- 总高度=5
删除图片2：
- 行1：图片1(2×2) + 图片3(2×2) → 行高=2
- 总高度=2
算法计算：
- pre_total[0]=0（无前行）
- 重新排版行1得max_h=2
- g[4]=0（无后续图）
- 总高度=0+2+0=2

注意事项

缩放计算：
- 使用整数运算：(h * space + w - 1) / w
- 避免浮点误差和性能开销
边界处理：
- 行内无图片时，行高为0
- 最后一行结束时j=N+1
性能优化：
- 每行最多处理100张图（因M≤100）
- 后缀数组g[]避免重复排版
内存优化：
- 数组大小设为100010（10⁵+10）
- 使用long long防溢出

题目描述

输入描述

输出描述

输入输出样例

示例

运行限制

算法思路

算法演示

算法步骤

代码实现（C++）

代码解析

实例验证

注意事项

相关文章：