自动搬运

查看原文

来自洛谷，原作者为

	newbeeglass AFO

搬运于2025-08-24 22:05:07，当前版本为作者最后更新于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;//养成好习惯 
}