Wpp

用户名：AbertW

访问量：3945

签　名：

等　　级
排　　名	841
经　　验	3490
参赛次数	1
文章发表	8
年　　龄	0
在职情况	学生
学　　校	北京工商大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-摆动序列-题解（C 代码规律）
浏览：472

Kruskal & Prim C++实现
浏览：180

C++ 区间筛法解决
浏览：271

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

蓝桥杯2017年第八届真题-图形排版-题解（C++代码）

　　作者: Wpp　　　　发表时间：2020-05-30 20:43:51 浏览：881　|　评论：1　

原题链接：蓝桥杯2017年第八届真题-图形排版

解此题的关键是每次去掉第i个图片后，1到i-1图片的排版不变，只要考虑i+1到N张图片排版的高度即可。
(参考了https://blog.csdn.net/qq_20087731/article/details/106262655
这位朋友的代码)

具体到代码实现时用一个数组Rev[]记录加入 i+1 到 N 图片的高度；顺序计算1到i-1图片排版的高度，接着计算 i+1到N的高度 (先把当前剩余宽度用i之后的图片排版，到下一行后加上Rev[]对应的值即可)

实现代码：

//解此题的关键是去掉一个图片i后,1-i-1的排版不发生变化
    //只要考虑 i+1 - N 的图片排版就可以了
    //首先考虑 以 i - N的顺序加入图片的高度 Rever[i]
    //接着只要一边顺序记录 1-i-1的高度,在加上 i+1 - N 的高度
    //每次都取最小,即得解
    //这里实现时都是记录排版一行的高度  
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int Max_N = 100000;
    const int INF = 1000000;
    
    struct paper//纸张结构体 
    {
    	int w;
    	int h;
    	paper(int w_,int h_){//构造函数 
    		w = w_;	h = h_;
    	}
    	paper(){}
    };
    paper P[Max_N+1];
    //输入
    int N,M;
    int Rev[Max_N+2];//Rev[i]: 将 i-N 顺序加入最后的高度 
    
    void add(paper &p,int k)//在p的基础上加入第k个图片 p记录当前占用宽度和高度 
    { //加入时分两种情况考虑 
    	if( p.w+P[k].w <= M )//加入图片宽度小于等于剩余宽度 (这时图片不需要收缩)
    	{
    		p.w += P[k].w;
    		p.h = max( p.h, P[k].h );
    	}
    	else
    	{//加入图片宽度>剩余宽度 
    		int w = M - p.w;//剩余宽度 
    		p.h = max( p.h, ((w*P[k].h-1)/P[k].w+1) );// wi/hi=w/h->h=w*hi/wi (-1,+1是处理向上取整)
    		p.w = M;
    	}
    } 
    
    int getRev(paper p,int k)//在加入p的基础上加上k-N后排版的高度 
    {
    	while( p.w<M && k<=N )
    	{
    		add(p,k);
    		k++;
    	}
    	return p.h + Rev[k];
    }
    
    void solve()
    {
    	for(int i=N; i>=1; i--)//初始化Rev[]
    	{
    		paper p(0,0);
    		Rev[i] = getRev(p,i);
    	}
    	
    	paper p(0,0);
    	int res = INF, h = 0;
    	for(int i=1; i<=N; i++)
    	{//每次去掉第i个图片 
    		res = min( res, h + getRev(p,i+1) );//h:1-i-1的高度, getRev(p,i+1):i+1-N高度 
    		add(p,i);	
    		if( p.w==M )
    		{
    			h += p.h;//更新当前排版高度 
    			p.w = p.h = 0;//下一行 
    		}
    	}
    	
    	printf("%d\n",res);
    }
    
    int main()
    {
    	scanf("%d%d",&M,&N);
    	for(int i=1; i<=N; i++){
    		scanf("%d%d",&P[i].w,&P[i].h);
    	}
    	
    	solve();
    	
    	return 0;
    }

//如果有表述不清或者不懂的地方欢迎留言

0.0分

4 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

往人

请问主函数里循环的ADD函数的作用是什么

2024-01-08 17:46:40

Wpp

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C二级辅导-计负均正（C语言代码）

Biggest Number （C++代码）回溯法

震宇大神的杀毒软件（C++代码）

蓝桥杯2017年第八届真题-图形排版-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

完数（C语言代码）

简单的a+b （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

A+B for Input-Output Practice （C语言代码）

1050题解（结构体数组与结构体指针的使用）

Wpp

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C二级辅导-计负均正 （C语言代码）

Biggest Number （C++代码）回溯法

震宇大神的杀毒软件 （C++代码）

蓝桥杯2017年第八届真题-图形排版-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

完数 （C语言代码）

简单的a+b （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

A+B for Input-Output Practice （C语言代码）

1050题解（结构体数组与结构体指针的使用）

C二级辅导-公约公倍（C语言代码）

C二级辅导-计负均正（C语言代码）

震宇大神的杀毒软件（C++代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

完数（C语言代码）