题目链接:1.图形排版 - 蓝桥云课 (lanqiao.cn)
本道题暴力算法思路是挨个选择不放入当前图片,但是很显然不可能满分。因此考虑优化:在暴力的过程中每次重新选择一个图片放入当前行,只有这一行是需要重新计算的,后续的行数高度是被重复使用的,因此可以进行预处理,计算出使用第i张图片作为行首的后续所有图片的高度。这样就大大减少了计算量。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int W[N] = {0},H[N]={0};
int st[N] = {0};//表示从第i个开始作为首行铺设的高度
int n=0,M=0;
void solve(int &now,int &w,int &h)//注意此处为引用,便于在调用函数中使用其他变量
//这里的函数通过设置多个变量,为不同用途的使用提供方便
//多使用函数:维护方便,使用方便。
{
while(now<n) //对当前行进行填充,至填满或者排版完成
{
if(W[now]+w<M)
{
w+=W[now];//更新数据
h = max(h,H[now]);
}
else//最后一个图片需要缩放
{
h = max(h,(int)ceil(H[now]*(M-w)*1.0/W[now])); //注意这里使用向上取整前
//要将分子/分母变为浮点数类型,否则直接向下取整了
//而且要在运算过程中改变数据类型,而不是计算出结果后
w++;
now++;
break;
}
now++;
}
}
int calc(int now,int w,int h)//从当前行(宽度高度均已知)开始铺设
{
solve(now,w,h); //因为是引用传送数据,所以now会动态改变
return h+st[now];//返回填充完当前行的高度以及后续几行的高度之和
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//输入数据很多需要优化
cin>>M>>n;
for(int i=0;i<n;i++)//录入数据
{
cin>>W[i]>>H[i];
}
//进行预处理,
st[n] = 0;
for(int i=n-1;i>=0;i--)//倒序是因为处理过程中需要用到后续的值
{
st[i] = calc(i,0,0);
}
//在先前我们已经预处理完成以各个图片作为行首以及后续行的长度
//接下来只需要挨个考虑删除的照片并进行筛选即可
//1.不放第i张,并从当前行开始铺设
//2.将第i张放入用于下一轮计算
int pre_h=0,nw=0,nh=0,ans=INT_MAX;//不包括当前行的高度,当前行的宽度高度
//选出最小值应该初值很大
for(int i=0;i<n;i++){
//1. 不放当前图片
ans = min(ans,pre_h+calc(i+1,nw,nh));
//2. 放入当前图片
if(W[i]+nw<M)
{
nw+=W[i];//更新数据
nh = max(nh,H[i]);
}
else//最后一个图片需要缩放
{
nh = max(nh,(int)ceil(H[i]*(M-nw)*1.0/W[i])); //注意这里使用向上取整前
//要将分子/分母变为浮点数类型,否则直接向下取整了
//而且要在运算过程中改变数据类型,而不是计算出结果后
nw = 0;
pre_h +=nh;//注意更新
nh = 0;
}
}
cout<<ans<<endl;
return 0;
}