P4904题解

newbeeglass · 2022-07-15 20:43:39 · 题解

一开始以为这是一道找规律的题，后面发现 n\le900 ，所以想到了枚举。

大矩形的面积一定为 12n ，所以可以先枚举一条边，再定另一条边。具体枚举的方式如下：

因为要找两边最接近的，那就从正方形开始，也就是从 i=\sqrt{n} 开始，一直减到 3 ，因为首先要满足边接近，所以此时第一个找到的符合题意的答案就是最终答案，直接 break 就好了。

我们可以先定一条边为 a ，另一条边为 b ，因为都为整数，且 a\times{b}=12n ，所以 a 和 b 中要么一个是 12 的倍数，要么一个是 3 的倍数，另一个是 4 的倍数，所以我们可以先定一条边比如 a 是 3 的倍数，那么 b 就可以分解为 4x+3y ，此时就又可以通过枚举的方式判断 b 是否合法存在（ x 和 y 都是整数）。

全部判断合法后，开始记录旋转照片的数量。前面我们已经将 b 分解为 4x+3y ，如果 b 作为纵向边，那么一列上旋转过的矩形就有 x 个，可以自行模拟一下，每列纵向摆放的矩形数量都是一样的，所以最终旋转的矩形数为 \frac{ax}{3} ，当 a 为纵向边时，旋转数与前者相加一定正好等于总数 n ，是 n-\frac{ax}{3} 。

AC code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int ans=0x3f;
    int n;
    bool flag=0;
    cin>>n;
    int s=sqrt(12*n);//从s开始枚举 
    for(int i=s;i>=3;i--){
        if((12*n)%i==0){//i肯定是整数，保证另一边是整数再进行运算 
            int a,b;
            if(i%3==0){
                a=i;
                b=(12*n)/i;
            }
            else{
                b=i;
                a=(12*n)/i;
            }
            for(int j=0;j<=b/4;j++){
                if((b-4*j)%3==0){//保证其为整数 
                    ans=min(ans,j*a/3);
                    ans=min(ans,n-j*a/3);//由于我只将a作为3的倍数的边，所以两种情况都要判断
                    flag=1; 
                }
            }
        }
        if(flag){
            break;//找到的就是边长最接近的，直接break 
        }
    }
    cout<<ans;
    return 0;//养成好习惯 
}