侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-27 / 0 评论 / 0 点赞 / 76 阅读 / 2,577 字 / 正在检测是否收录...

题目

试题 历届真题 图形排版【第八届】【省赛】【C组】

3161. 图形排版


小明需要在一篇文档中加入 NN 张图片,其中第 ii 张图片的宽度是 WiW_i,高度是 HiH_i

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

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

0123456789
----------
111
111  333
11122333
11122333

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

0123456789
----------
        44
111     44
111  33344
1112233344
1112233344

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

0123456789
----------
        44
111     44
111  33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777

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

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

输入格式

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

接下来 NN 行,每行 22 个整数 Wi,HiW_i, H_i,表示第 ii 个图大小为 Wi×HiW_i \times H_i

输出格式

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

数据范围

1N1051 \le N \le 10^5,
1M,Wi,Hi1001 \le M,W_i,H_i \le 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

输出样例2:

17

解题

方法一:暴力 模拟(TLE)

思路

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

其中在缩放图片的时候,高度需要进行向上取整:xy=(x+y1)/y\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);
    }
}

方法二:模拟

思路

倒序预先处理出一个数组 ff[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;
}
0

评论区