【模拟】图形排版【蓝桥杯】

题目

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

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

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

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

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

现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 $N$ 张图片中选择一张删除掉以降低总高度。

他希望剩余 $N-1$ 张图片按原顺序的排版高度最低，你能求出最低高度是多少么？

输入格式

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

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

输出格式

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

数据范围

$1 \le N \le 10^5$ ,
$1 \le M,W_i,H_i \le 100$

输入样例1：

输出样例1：

输入样例2：

输出样例2：

解题

方法一：暴力模拟(TLE)

思路

直接按照题目模拟，把所有图片读入数组后，枚举数组中每一张图尝试删除该图后进行排版并统计高度，并维护一个最小的高度(minHeight)，尝试完所有可能后就能得到删除一张图排版的最低高度。

其中在缩放图片的时候，高度需要进行向上取整： $\lceil \frac{x}{y} \rceil = (x + y - 1) / y$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int M = (int) in.nval;
        in.nextToken();
        int N = (int) in.nval;
        int[][] images = new int[N][2];
        for (int i = 0; i < N; ++i) {
            in.nextToken();
            images[i][0] = (int) in.nval;
            in.nextToken();
            images[i][1] = (int) in.nval;
        }
        int minHeight = Integer.MAX_VALUE;
        for (int del = 0; del < N; ++del) {
            // 尝试删除 images[del]
            int totalHeight = 0;
            int w = 0, h = 0;
            for (int i = 0; i < N; ++i) {
                if (i == del) continue;
                int imgWidth = images[i][0], imgHeight = images[i][1];
                if (imgWidth > M - w) {
                    // 缩放图片时高度向上取整
                    h = Math.max(h, (imgHeight * (M - w) + imgWidth - 1) / imgWidth);
                    w = M;
                } else {
                    h = Math.max(h, imgHeight);
                    w += imgWidth;
                }
                // 排满该行后换行
                if (w == M) {
                    w = 0;
                    totalHeight += h;
                    h = 0;
                }
            }
            totalHeight += h;
            // 维护排版的最小高度
            if (totalHeight < minHeight) minHeight = totalHeight;
        }
        System.out.println(minHeight);
    }
}

方法二：模拟

思路

倒序预先处理出一个数组 f，f[i] 表示：起一张新纸然后从第 i 张图片开始把后面所有图片全部排上去后得到的高度。然后按顺序枚举每一张图片尝试除此以外把其他图片放入，其中预处理与求解的过程中可以共用一个“放满一行”的函数。

具体思路见代码注释。

参考：https://www.bilibili.com/video/BV1QE411E7ft?p=91

代码

import java.io.*;
public class Main {
    static class Image {
        int w, h;
        
        Image(int w, int h) {
            this.w = w;
            this.h = h;
        }
    }

    static class Line {
        int w, h;

        Line() { this(0, 0); }

        Line(int w, int h) {
            this.w = w;
            this.h = h;
        }

        // 向该行中放入一张图片
        void add(Image img) {
            // 为压缩图片时防止修改原图 需要拷贝宽高出来用于修改
            int imgWidth = img.w, imgHeight = img.h;
            if (w + imgWidth > M) {
                // 高度向上取整 解释见方法一
                imgHeight = (imgHeight * (M - w) + imgWidth - 1) / imgWidth;
                imgWidth = M - w; // 宽度压到该行剩余宽度
            }
            this.w += imgWidth;
            this.h = Math.max(this.h, imgHeight);
        }

        // 判断该行是否已满
        boolean isFull() {
            return this.w == M;
        }
        
        // 判断该行是否为空(新行)
        boolean isEmpty() {
            return this.w == 0 && this.h == 0;
        }

        // 清空该行
        void clear() {
            this.w = 0;
            this.h = 0;
        }

        // 拷贝该行
        Line copy() {
            return new Line(this.w, this.h);
        }
    }

    static int M, N;
    static Image[] imgs;
    static int[] f; // 辅助数组 用处类似递归中的memo数组 用于减少重复计算

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        M = (int) in.nval;
        in.nextToken();
        N = (int) in.nval;
        imgs = new Image[N];
        f = new int[N];
        for (int i = 0; i < N; ++i) {
            in.nextToken();
            int w = (int) in.nval;
            in.nextToken();
            int h = (int) in.nval;
            imgs[i] = new Image(w, h);
        }
        // 输入数据结束
        // 倒序预处理数组 f[i]表示起一张信纸起一张新纸然后从第i张图片开始把后面所有图片全部排上去后得到的高度
        for (int i = N - 1; i >= 0; --i) f[i] = addTillFull(new Line(), i);
        // 新建一个空行用来模拟 这个行相当于一个滚动行用于模拟整张纸
        Line line = new Line();
        int minHeight = Integer.MAX_VALUE, totalHeight = 0; // 记录累计的总高度
        // 尝试插入除了第del张照片以外的其他照片
        for (int del = 0; del < N; ++del) {
            /* newHeight是指把从第del+1张图开始后面的所有图插入之前的累积的行(line)中
             * 并拿到其高度然后加上之前累积行的高度 (注意：这个累积行需要拷贝一份新的用再拿去模拟
             * 因为模拟插入会改变行中的内容，而原始的累积行在之后还有用，不能被修改
             * 这里totalHeight不能直接改，而是要再新建一个newHeight也是同样的理由
             */
            int newHeight;
            // 如果该行为空 就相当于直接在新行中放入del+1与后面的图 这不就是f[del+1]的定义嘛
            // 所以可以直接利用辅助数组f拿到填充后高度(注意保证数组不能越界)
            if (line.isEmpty() && del + 1 < N) newHeight = totalHeight + f[del + 1];
            // 否则就需要利用addTillFull函数来做上面注释里说的步骤
            else newHeight = totalHeight + addTillFull(line.copy(), del + 1);
            // 更新排版的最小高度
            minHeight = Math.min(minHeight, newHeight);
            
            // 这之后就是在为下一次循环服务了
            // 把第del张图片添加到累积行中
            line.add(imgs[del]);
            // 如果累积行满了需要及时结算该行高度加入累积高度
            if (line.isFull()) {
                totalHeight += line.h;
                // 然后把该行清空以便下一次循环的模拟
                line.clear();
            }
        }
        System.out.println(minHeight);
    }

    // 把第k张图片及之后的所有图片放入到line行中并返回其高度
    static int addTillFull(Line line, int k) {
        // 实际上我们只需要把line这行放满就行了
        for (; k < N && !line.isFull(); ++k) line.add(imgs[k]);
        // 之后可以利用辅助数组拿到：把line行填满后的第一张图片及其之后的图片放入一个新行后得到的高度
        // 然后把line行的高度加上辅助数组拿到的高度然后返回即可
        // 如果line行填满后的第一张图片已经没了的话(k越界了)就直接返回line行的高度就行了
        return k < N ? line.h + f[k] : line.h;
    }
}

C++ 中由于我们预先分配的数组长度比较大而且初始化为 0，所以中间的两个在 Java 中可能导致数组越界的问题可以不必理会，然后是 C++ 中注意一下引用传递和值传递的问题写起来比 Java 方便，其余的代码与 Java 几乎一样。

#include <iostream>

using namespace std;

const int MAX_N = 1e5 + 10;
int N, M;
int f[MAX_N];

struct Image {
    int w, h;
} imgs[MAX_N];

struct Line {
    int w, h;

    Line(int w = 0, int h = 0): w(w), h(h) { }

    Line operator+(const Image& img) {
        int img_w = img.w, img_h = img.h;
        if (w + img_w > M) {
            img_h = (img_h * (M - w) + img_w - 1) / img_w;
            img_w = M - w;
        }
        return Line(w + img_w, max(h, img_h));
    }

    Line operator+=(const Image& img) {
        return *this = *this + img;
    }

    bool full() {
        return w == M;
    }

    bool empty() {
        return w == 0 && h == 0;
    }

    void clear() {
        w = 0;
        h = 0;
    }
};

int addTillFull(Line line, int k) {
    for (; !line.full() && k < N; ++k) line += imgs[k];
    return line.h + f[k];
}

int main() {
    scanf("%d%d", &M, &N);
    for (int i = 0; i < N; ++i) scanf("%d%d", &imgs[i].w, &imgs[i].h);
    for (int i = N - 1; i >= 0; --i) f[i] = addTillFull(Line(), i);
    Line line; 
    int min_height = 0x3f3f3f3f, total_height = 0;
    for (int del = 0; del < N; ++del) {
        int new_height = total_height + (line.empty() ?
            f[del + 1] : addTillFull(line, del + 1));
        min_height = min(min_height, new_height);
        line += imgs[del];
        if (line.full()) {
            total_height += line.h;
            line.clear();
        }
    }
    printf("%d\n", min_height);

    return 0;
}

目录CONTENT

【模拟】图形排版【蓝桥杯】

题目

解题

方法一：暴力模拟(TLE)

思路

代码

方法二：模拟

思路

代码

评论区

【模拟】图形排版【蓝桥杯】

题目

解题

方法一：暴力 模拟(TLE)

思路

代码

方法二：模拟

思路

代码

评论区

方法一：暴力模拟(TLE)