[题解] hihocoder – 1365 图片排版

Contents

1 问题描述
2 输入格式
3 输出格式
4 样例输入
5 样例输出
6 解题思路
7 代码

问题描述

小明需要在一篇文档中加入 $N$ 张图片，其中第 $i$ 张图片的宽度是 $W_i$，高度是 $H_i$。
假设纸张的宽度是 $M$，小明使用的文档编辑工具会用以下方式对图片进行自动排版：

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

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

如果当前行剩余宽度为 $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$。
对于 $30 \%$的数据，满足 $1 \leq N \leq 1000$
对于 $100 \%$ 的数据，满足 $1 \leq N \leq 100000，1 \leq M, W_i, H_i \leq 100$

输出格式

输出在删除掉某一张图片之后，排版高度最少能是多少。

样例输入

样例输出

解题思路

考虑能否求出以 $x$ 号图片开头一直到结尾的高度，用 $sum[x]$ 表示

考虑暴力统计以 $x$ 为开头的一行高度，然后可以求得下一行开头为 $v$，那么

$$sum[x] = h + sum[v]$$

然后用一个数组 $pre$ 统计 $x$ 号图片之前所有行的高度

那么对于删除一个数 $x$，我们可以用之前所有行的高度，加上暴力统计这一行的高度，加上后缀统计，求最大值即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int m, n;
int w[MAXN], h[MAXN];
int pre_h[MAXN], line[MAXN], End[MAXN];
int sum[MAXN];

inline int calc(int a, int b, int c){
    return ceil((long double) (a * c) / b);
}

int main(){

    m = read();
    n = read();

    for(register int i=1; i<=n; i++){
        w[i] = read();
        h[i] = read();
    } 

    int tmp_n = 1;
    int rest = m;
    int high = 0;
    int now = 1;

    while(true){
        if(now > n){
            break;
        }
        if(rest >= w[now]){
            line[now] = tmp_n;
            high = max(high, h[now]);
            rest -= w[now];
            now++; 
        }else if(rest == 0){
            End[tmp_n] = now-1;
            pre_h[tmp_n] = pre_h[tmp_n - 1] + high;
            high = 0;
            rest = m;
            tmp_n++;
        }else{
            line[now] = tmp_n;
            high = max(high, calc(h[now], w[now], rest));
            rest = 0;
            now++;
        }
    }

    for(register int i=n; i>=1; i--){
        rest = m;
        now = i;
        high = 0;

        while(true){
            if(now > n)
                break;

            if(rest >= w[now]){
                high = max(high, h[now]);
                rest -= w[now];
                now++;
            }else if(rest == 0){
                break;
            }else{
                high = max(high, calc(h[now], w[now], rest));
                rest = 0;
                now++;
            }
        }

        sum[i] = high + sum[now];
    }

    int ans = 0x3f3f3f3f;
    int tmp = 0;

    for(register int i=1; i<=n; i++){
        tmp = 0;

        int delete_line = line[i] - 1;
        tmp += pre_h[delete_line];

        rest = m;
        high = 0;
        now = End[delete_line] + 1;

        while(true){
            if(now > n)
                break;

            if(now == i){
                now++;
                continue;
            }

            if(rest >= w[now]){
                high = max(high, h[now]);
                rest -= w[now];
                now++;
            }else if(rest == 0){
                break;
            }else{
                high = max(high, calc(h[now], w[now], rest));
                rest = 0;
                now++;
            }           
        }

        tmp += high;
        tmp += sum[now];
        ans = min(ans, tmp);
    }

    printf("%d", ans);
    return 0;
}