自动搬运

查看原文

来自洛谷，原作者为

	无名之雾 I LOVE KaFKa forever

搬运于2025-08-24 22:26:04，当前版本为作者最后更新于2024-01-17 21:57:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[NWRRC2016] Folding 题解

题意

给出一个 $W \times H$ 的矩形，问你经过多少次的折叠后才可以变成一个 $w \times h$ 的矩形。

思路

本题没有什么思维上的难点，只需按部就班的模拟不断将 $W$ 和 $H$ 除以 $2$ 直到符合题意，输出操作次数即可。

坑点

1. 本题并没有保证 $W \ge w$，$H \ge h$。所以应在开头特判，如若 $W < w$，或 $H < h$ 直接输出 $-1$。

2. 如果你的操作过程是不断将 $w$ 和 $h$ 乘 $2$ 那么没事。但如果是将 $W$ 和 $H$ 不断除以 $2$ 逼近 $w$ 和 $h$，则需要开浮点类型。我是绝对不会告诉你我就是这样WA的。

代码

#include<bits/stdc++.h>
using namespace std;
#define int double //一定要开double！！
#define s(w,h) if(w>h)swap(w,h)
#define wh(x,y,cnt) while(x>y)x/=2,cnt++;
signed main(){
    int W,H,w,h;
    cin>>W>>H>>w>>h;
    s(W,H);s(w,h); //更换长宽位置
    if(W<w||H<h)cout<<-1; //特判
    else{
       int a=W,b=H,cnt1=0,cnt2=0;
	    wh(a,w,cnt1);wh(b,h,cnt2);
	    if(W<h)cout<<cnt1+cnt2;
	    else{
	        int cnt3=0,cnt4=0;
	        swap(w,h);wh(W,w,cnt3);wh(H,h,cnt4);
	        cout<<min(cnt1+cnt2,cnt3+cnt4);
	    }
    }
    return 0;
}