折纸(folding)

问题 C: 折纸

时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]

题目描述

现有一个W*H的矩形纸张，求至少要折多少次才能使矩形纸张变成w*h的矩形纸张。注意，每次的折痕都要平行于纸张的某一条边。

输入

第一行，包括两个整数W，H。
第二行，包括两个整数w，h。

输出

输出一个整数，表示至少需要折的次数。若无解，则输出-1。

样例输入 Copy

【样例1】
2 7
2 2
【样例2】
5 5
1 6
【样例3】
10 6
4 8

样例输出 Copy

【样例1】
2
【样例2】
-1
【样例3】
2

提示

对于20%的数据，W=w且H,h<=3。
对于100%的数据，1<=W,H,w,h<=10⁹。

从这题开始，请注意：前方高能！

比赛的时候，我在纸上画了几下，发现当边长是W时，把它对折一下为W/2，如果期望达到的w在W和W/2的范围之内，那么就是可以的，否则，就要折成W/2。

但是看到了最后一个样例，他们的边长需要反过来才能够折，于是自认为很“机智”地就用swap把大小调整好，大对大，小对小。事实证明是个大错误。

错误点get

1、不能直接变成W/2，因为当是7的时候，7/2=3，但是并不能折到3，应该最小是4。所以应该是(W+1)/2,同样的，用偶数实验也是可行的。

2、至于大对大，小对小的思路显然是想少了。赛后同学给我举了个例子，5 7折成4 5。如果是用我的方法，那么5折成4要折一次，7折成5也要折一次，一共就是两次。

但如果是5对5，那么根本不用折，7对4，这一次就可以了。最优解应该是一次。

我看似很有道理的理论就over了。

正解其实和这个差不了多少，就是分别算一下两种对应的情况，取一个min为最优解即可。

时间复杂度 O（log(10^9)）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map> 
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int maxn=1e6; 
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n,m,x,y;
void inint(){
    cin>>n>>m>>x>>y;
}
int main(){
        inint();     
        ll sum=0;
        ll nn=n,mm=m;
        if((x>n&&x>m)||(y>n&&y>m)||(n<x&&n<y)||(m<y&&m<x)) {
            cout<<-1<<endl;
            return 0;
        }
        if(n>=x&&m>=y) {
            while(n>x) {
                sum++;
                n-=n/2;
            }
            while(m>y) {
                sum++;
                m-=m/2;
            }
        } else sum=maxn;
        swap(x,y);
        ll s=0;
         if(nn>=x&&mm>=y) {
            while(nn>x) {
                s++;
                nn-=nn/2;
            }
            while(mm>y) {
                s++;
                mm-=mm/2;
            }
        }else s=maxn;
            cout<<min(sum,s)<<endl;
}