[NWRRC2016] Folding 题解

· · 题解

[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;
}