标题：图形排版
小明需要在一篇文档中加入 N 张图片，其中第 i 张图片的宽度是 Wi，高度是 Hi。
假设纸张的宽度是 M，小明使用的文档编辑工具会用以下方式对图片进行自动排版：
1. 该工具会按照图片顺序，在宽度 M 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 M=10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为4。(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第x张图片占用的版面)
0123456789
----------
111
111 333
11122333
11122333
- 如果当前行剩余宽度大于0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张4x9的图片，由于剩余宽度是2，这张图片会被压缩到2x5，再被放入第一行的末尾。此时该行高度为5：
0123456789
----------
44
111 44
111 33344
1112233344
1112233344
3. 如果当前行剩余宽度为0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 N 张图片的排版高度。例如再放入11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为11：
0123456789
----------
44
111 44
111 33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777
现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 N 张图片中选择一张删除掉以降低总高度。他希望剩余N-1张图片按原顺序的排版高度最低，你能求出最低高度是多少么？
输入：
第一行包含两个整数 M 和 N，分别表示纸张宽度和图片的数量。
接下来 N 行，每行2个整数Wi, Hi，表示第 i 个图大小为 Wi*Hi。
对于30%的数据，满足1<=N<=1000
对于100%的数据，满足1<=N<=100000，1<=M, Wi, Hi<=100
输出：
一个整数，表示在删除掉某一张图片之后，排版高度最少能是多少。
样例输入：
4 3
2 2
2 3
2 2
样例输出：
2
另一个示例，
样例输入：
2 10
4 4
4 3
1 3
4 5
2 1
2 3
5 4
5 3
1 5
2 4
样例输出：
17
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
解析：
//自定义类型存储图形的宽高
class MyShape
{
int width; //宽
int height; //高
}
public class Demo10
{
public static void main(String[] args)
{
List<MyShape> listShape = new ArrayList<MyShape>(); //定义形状集合
Scanner input = new Scanner(System.in);
int paperWidth = input.nextInt(); //输入纸张宽度
int picNum = input.nextInt(); //输入形状图片数量
//循环输入每个图形的宽与高
for (int i = 1; i <= picNum; i++)
{
MyShape myShape = new MyShape();
myShape.width = input.nextInt();
myShape.height = input.nextInt();
listShape.add(myShape);
}
int[] arr_sum_max_height = new int[picNum]; //定义数组存储删除每张图后的最大高度
for (int i = 0; i < listShape.size(); i++) //控制删除每张图片
{
int sy_width = paperWidth; //纸张剩余宽度=纸张的原始宽度
int row_max_height = 0; //纸张的当前行最大高度
int sum_max_height = 0; //纸张的总体最大高度
//循环往纸张上放入图形
for (int j = 0; j < listShape.size(); j++)
{
int s_width = listShape.get(j).width; //存储当前图片宽度
int s_height = listShape.get(j).height; //存储当前图片高度
//忽略删除的图片
if(i == j)
continue;
//当剩余宽度大于等于当前形状的宽度的时候,直接在右边放入图片
if(sy_width > s_width)
{
if(row_max_height < s_height)
row_max_height = s_height; //跟新最大高度值
sy_width = sy_width - s_width; //跟新纸张剩余宽度
continue;
}
//当剩余宽度正好等于当前形状宽度的时候
if(sy_width == s_width)
{
if(row_max_height < s_height)
row_max_height = s_height; //跟新最大高度值
sy_width = paperWidth; //跟新下一行纸张剩余宽度
sum_max_height += row_max_height; //累加总高度
row_max_height = 0; //跟新下一行的纸张最大高度
continue;
}
//当纸张剩余宽度小于当前形状宽度的时候，缩放后在进行存放
if(sy_width > 0 && sy_width < s_width)
{
//图形宽度/剩余宽度 = 图形高度/纸张占用高度，所以
//纸张占用高度 = 图形高度/(图形宽度/剩余宽度)
int height = (int)Math.ceil((s_height*1.0)/((s_width*1.0)/(sy_width*1.0)));
if(row_max_height < height)
row_max_height = height; //跟新最大高度值
sy_width = paperWidth; //跟新下一行纸张剩余宽度
sum_max_height += row_max_height; //累加总高度
row_max_height = 0; //跟新下一行的纸张最大高度
}
}
//测试删除每个图形后的最大高度
//System.out.println(sum_max_height+row_max_height);
//此时需要+row_max_height，因为sum_max_height只是存储整行宽度排版完成之后的最大值，
//也就是当前行上面所有行的最大高度。
arr_sum_max_height[i] = sum_max_height+row_max_height;
}
//求arr_sum_max_height数组的最小值即是最终结果。
int min = Integer.MAX_VALUE;
for (int j = 0; j < arr_sum_max_height.length; j++) {
if(min > arr_sum_max_height[j])
min = arr_sum_max_height[j];
}
System.out.println(min);
}
}
备注：此题采取假设每个图形是被忽略的，依次算出最大高度，然后在所有的最大高度中取最小值。
网友评论