题目大意是给定一个n*m的矩形，求将其分割，使得每个小矩形都有边在大矩形的边上。其中一个坐标(x,y)的矩形不能使用，问切割后的最大面积最小能是多小？ 显然，要使大矩形的边界得到充分的利用，应该将切割成1*len的矩形。在没有(x,y)使用限制的情况下，ans=min(n+1,m+1)/2，全竖分割或者全横分割。 在有使用限制情况下，可以分成 全竖分割：ans=max(max(x-1,n-x),(n+1)/2); 全横分割：ans=max(max(y-1,m-y),(m+1)/2); 部分竖割，剩余横割：ans=max(max(x,n-x+1),(m+1)/2); 部分横割，剩余竖割：ans=max(max(y,m-y+1),(n+1)/2); 另外需要特判，当n=m且(x,y)位于大矩形正中心时，ans=min(n+1，m+1)/2-1。
#include<map>#include<cmath>#include<ctime>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#define LL long longusing namespace std;const int maxn=10005;const LL Inf=1e18;int n, m, x, y;void solve(){ if(n>m){ swap(n,m); swap(x,y); } int ans=(n+1)/2; if(n==m&&m%2&&2*x-1==n&&2*y-1==m){ PRintf("%d/n",ans-1); return; } int ans1=max(max(x-1,n-x),(n+1)/2);// int ans2=max(max(y-1,m-y),(m+1)/2); int ans3=max(min(x,n-x+1),(m+1)/2); int ans4=max(min(y,m-y+1),(n+1)/2); ans1=min(ans1,ans2); ans3=min(ans3,ans4); printf("%d/n",min(ans1,ans3));}int main(){// freopen("matrix.in","r",stdin);//从in.txt中读取数据// freopen("matrix.out","w",stdout);//输出到out.txt文件 while(~scanf("%d%d%d%d",&n,&m,&x,&y)){ solve(); } return 0;}新闻热点
疑难解答
