AcWing 3161. 图形排版
原题链接
简单
作者:
静静在Coding
,
2023-01-09 19:50:45
,
所有人可见
,
阅读 261
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 100010;
struct Pict{
int w,h;
}p[N];
int f[N];//f[i] i ~ n的卡片顺序排列的高度
int w,n;
int get(int wide,int k,int &h){
for(;k < n;k++){
if(wide < p[k].w){
h = max(h,(int)ceil((double)p[k].h*wide/p[k].w));
wide = 0;
}else{
h = max(h,p[k].h);
wide -= p[k].w;
}
if(wide == 0) return k + 1;
}
return k;
}
int main()
{
cin>>w>>n;
for(int i = 0;i < n;i++){
cin>>p[i].w>>p[i].h;
}
for(int i = n - 1;i >= 0;i--){
int h = 0;
int k = get(w,i,h);
f[i] = h + f[k];
}
//height 一行排列好的总高度 lheight 当前行的最高的高度 width 当前这一行的还剩的宽度
int height = 0,lheight = 0,wide = w;
int res = 1e7; //数据 1e5 * 100
for(int i = 0;i < n;i++){
int h = lheight;
int k = get(wide,i + 1,h);
res = min(res,h + f[k] + height);
if(p[i].w > wide){
lheight = max(lheight,(int)ceil((double)p[i].h*wide/p[i].w));//要向上取整
wide = 0;
}else{
lheight = max(lheight,p[i].h);
wide -= p[i].w;
}
if(wide == 0){ //换新的一行
wide = w;
height += lheight;
lheight = 0;
}
}
cout<<res<<endl;
return 0;
}