图形排版详细题解

注意

该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。另外为了节省篇幅，代码中不再写明#include，如果遇到我没有声明的函数，那么就是某一个头文件中的函数，读者搜索“c + 函数名字”就能查到相关信息。

题目

小明需要在一篇文档中加入N张图片，其中第i张图片的宽度是W_i，高度是H_i。

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

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

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

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

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

输入格式

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

接下来N行，每行2个整数W_i, H_i，表示第i个图大小为W_i * H_i。

对于30%的数据，满足1 <= N <= 10³。

对于100%的数据，满足1 <= N <= 10⁵，1 <= M, W_i, H_i <= 100。

输出格式

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

样例

查看样例

样例输入1

4 3
2 2
2 3
2 2

样例输出1

2

样例输入2

2 10
4 4
4 3
1 3
4 5
2 1
2 3
5 4
5 3
1 5
2 4

补充信息

代码长度限制：16KB
时间限制：1000ms
内存限制：64MB

思路

看到这道题第一反应还是贪心（~~罪孽深重的贪心~~），找到能让当前行减少最多的一个图片删掉。随后发现和样例答案不一样，仔细思考一下突然发现，还要考虑删除图片后后面的图片要往前补。

接下来显然只能枚举了，把所有图片都删除一遍，找到最终结果最小的就是答案。

现在我们再来分析一下这道题。首先我们肯定需要存储输入的数据，这里我选择使用结构体存储；然后我们还需要有缩放图片这一功能，直接在结构体里面写一个zoom方法就可以了；最后再遍历所有可能就可以了。

随即我便写了一个枚举（代码如下），但是出乎意料的是竟然段错误了：

#include <bits/stdc++.h>

using namespace std;

struct Image {
	int width;
	int height;
	Image zoom(int maxWidth) {
		if (maxWidth < width) {
			double scale = width / (double) maxWidth;
            int newHeight = (int) (ceil(height / scale));
			return {maxWidth, newHeight};
		}
		return *this;
	}
};

int task(Image input[], int length, int width, int ignoreIndex) {
	int lineWidth = width;
	int maxHeight = 0;
	int sumHeight = 0;
	for (int i = 0; i != length; ++i) {
		if (i == ignoreIndex) continue;
		int maxWidth = min(lineWidth, input[i].width);
		Image value = input[i].zoom(maxWidth);
		lineWidth -= value.width;
		if (value.height > maxHeight) maxHeight = value.height;
		if (lineWidth == 0) {
			sumHeight += maxHeight;
			maxHeight = 0;
			lineWidth = width;
		}
	}
	return sumHeight + maxHeight;
}

int main() {
	Image input[105];
	int width, amount;
	cin >> width >> amount;
	for (int i = 0; i != amount; ++i) {
		scanf("%d %d", &input[i].width, &input[i].height);
	}
	int minHeight = INT_MAX;
	for (int i = 0; i != amount; ++i) {
		minHeight = min(minHeight, task(input, amount, width, i));
	}
	cout << minHeight;
	return 0;
}

然后我发现，原来是因为题上把10⁵打成了105。

这样看来，简单的暴力计算是不行的了，因为数据量大的时候必然会时间超限。我们必须想办法记录中间一部分数据减少计算量，这样才可以在给定时间内跑完结果。

现在我们来看有哪些量是反复计算的：

从第一个图片到删除图片所在行的上一行的高度
从删除图片所在行的下一行到最后一行的高度

现在我们的思路就清晰了，我们需要保存这两个信息。现在要思考的是怎么保存这两个信息，不难想到，以图片的下标为key值，表示如果以key为一行的起始，高度为多少。

知道了这些，我们至少要编写一个readRecCache的函数。再思考一下，我们发现两个可以缓存的信息有共通之处，都需要以行为单位进行计算，所以我们不妨以行为单位缓存信息。这样的话，我们便需要编写以下函数：

calculateLineCache
readLineCache
readRecCache

其中为什么需要有一个不带缓存的计算呢？因为删除图片所在的那一行肯定是不可以读取缓存需要重新计算的，为了避免代码重复我们直接提炼出来一个函数。

接下来还有一个问题，readRecCache内部应当采用哪种实现方法？是提前计算还是随用随计算？

答案是前者。假如我们采用随用随计算的方法，那么我们很容易想到使用递归的方式编写函数，但是这道题数据量很大，如果出现行数过多的情况，就很容易调用栈溢出；如果不采用递归函数又会变得很复杂。所以我们采用提前计算，即从后往前算，这其实就是后缀和的应用。

题解

首先，我们按照上面的分析，以此写出我们需要的结构体和函数：

struct image {
    int width, height;

    image zoom(int maxWidth) const {
        if (maxWidth >= width) return *this;
        double scale = width / (double) maxWidth;
        int newHeight = (int) (ceil(height / scale));
        return {maxWidth, newHeight};
    }
};

struct cache {
    //本次计算的终点（不包含）
    int next = -1;
    //计算的图片中的最大高度
    int height = 0;

    cache(int next, int height) : next(next), height(height) {}

    cache() = default;
};

int gWidth, gLength;
image input[100000];

//计算一行的内容
//参数：
//  start - 计算的起始下标（包含）
//  ignoreIndex - 要删除的图片下标
cache calculateCache(int start, int ignoreIndex = -1) {
    int lineWidth = gWidth;
    int maxHeight = 0;
    int next = gLength;
    for (int i = start ; i != gLength ; ++i) {
        if (i == ignoreIndex) continue;
        image pic = input[i].zoom(lineWidth);
        lineWidth -= pic.width;
        maxHeight = max(maxHeight, pic.height);
        if (lineWidth == 0) {
            next = i + 1;
            break;
        }
    }
    return {next, maxHeight};
}

//计算一行的内容（有缓存时直接返回缓存内容）
const cache& readLineCache(int start) {
    static cache gCache[100000];
    cache& result = gCache[start];
    if (result.next != -1) return result;
    result = calculateCache(start);
    return result;
}

//计算以指定图片为起始到结束的需要的高度（有缓存时直接返回缓存内容）
int readRecCache(int start) {
    static int gCache[100000];
    if (start == gLength) return 0;
    if (gCache[start] != 0) return gCache[start];
    auto& line = readLineCache(start);
    return gCache[start] = line.height + readRecCache(line.next);
}

接下来，我们需要写一个函数来实现功能：

//计算移除指定图片后的结果
//参数：
//  index - 要移除的图片的下标
//  upLineHeight - 上方已经计算的行高
//  start - 下一行的起始位置
int removePic(int index, int& upLineHeight, int& start) {
    //计算上半部分的行
    while (start != gLength) {
        cache& pic = readLineCache(start);
        if (pic.next < index) {
            upLineHeight += pic.height;
            start = pic.next;
        } else if (pic.next == index) {
            upLineHeight += pic.height;
            start = pic.next;
            break;
        } else break;
    }
    //计算包含要移除的图片的那一行
    cache nowLine = calculateCache(start, index);
    int result = upLineHeight + nowLine.height;
    //计算剩下的行
    result += readRecCache(nowLine.next);
    return result;
}

最后，写出main即可：

int main() {
    cin >> gWidth >> gLength;
    for (int i = 0 ; i != gLength ; ++i) {
        scanf("%d %d", &input[i].width, &input[i].height);
    }
    int result = INT_MAX;
    int upHeight = 0;
    int start = 0;
    for (int i = 0 ; i != gLength ; ++i) {
        result = min(result, removePic(i, upHeight, start));
    }
    printf("%d", result);
    return 0;
}

踩坑心计

你以为这就是所有了？有些心急的小伙伴可能已经把代码提交上去尝试了，结果会发现有答案错误，难道是题解写错了？其实是你没看完。

我刚开始这么写一直找不出来问题在哪，后来去蓝桥杯官网下载了测试数据，发现我算错的数据总是比答案稍微大一点点。然后我从四万行的输入数据里面一点点排查，总算找到了错在了什么地方。_{（看在我这么辛苦的份上不得打个赏支持下？）}

原来是zoom写的有问题，按照现在这种写法，如果图片宽高为：63 * 23，纸宽10，那么代码会把这个图片的高度缩放到31，但是实际上应该是30。

为什么会出现这个问题呢？其实是因为浮点误差，理想计算过程是这样的

1
2
3

scale = 23 / 10 = 2.3
temp = 63 / scale = 30
newHeight = ceil(temp) = 30

实际上却是这样的：

1
2
3

scale = 23 / 10 = 2.2999...
temp = 63 / scale = 30.000...04
newHeight = ceil(temp) = 31

发现问题了吧，现在就两个解决方案：

推荐这个方案的原因是鬼知道ceil啥时候再给你来一发暴击。

image zoom(int maxWidth) const {
    if (maxWidth >= width) return *this;
    double scale = width / (double) maxWidth;
    double newHeight = height / scale;
    int value = (int) newHeight;
    if (newHeight - value >= 1e-6) ++value;
    return {maxWidth, value};
}

image zoom(int maxWidth) const {
    if (maxWidth >= width) return *this;
    int newHeight = (int) (ceil(height * maxWidth / (double) width));
    return {maxWidth, newHeight};
}

现在结果就正确啦~

PTA测试结果

语言：C++(G++)
最长耗时：10ms
最大内存：1332KB

创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o