HDU 5301 Buildings 建公寓（逻辑，水）

　　　　　　　　　　

题意：有一个包含n*m个格子的矩阵，其中有一个格子已经被染黑，现在要拿一些矩形来填充矩阵，不能填充到黑格子，但是每一个填充进去的矩形都必须至少有一条边紧贴在矩阵的边缘（4条边）的。用于填充的矩形其中最大面积的一个的面积大小为B，要使得B最小，如何填充？

思路：

　　由于每个格子（除了黑格子）都必须被覆盖到，而且又要面积尽量小，那么最小就是宽为1的矩形了，只是长应该是多少？如果给的是个长方形矩阵，当没有黑格子时，大概只要宽的一半就可以了吧？可是就是有了黑格子，为了找个坑，必须给个黑格子，不然也太简单了吧？

　　首先要知道最中间那部分必须覆盖到，所以当无黑格子时，无论是长方还是正方矩阵，所用最大矩形的长至少要满足 wid/2才行。由于黑格子的存在，情况可能有变数，比如刚好坐落于wid/2的偏左一点，再加上height很大的话，wid/2不够用了。看下图：

					1
					2
					3
					4
					5
					6
					7
					8
					9
					10
					11
					12
1	2	3	4	5	x	*	*	*	*	*	*	*	*	*	*	*	*	*	*

　　考虑上面50*20的矩阵，假如x是黑格子，那么答案还是wid/2=20/2=10吗？？黄色的那4个玩意谁来覆盖？上方的又太远，下方又更远。

　　为了保证有人能覆盖到那片黄色区域，要么是右边的来覆盖，要么是上边的来覆盖，看谁近咯！这样还不够，可能距离上方只是2而已，距离右边是16，那么被我们选的是2，怎么可能够用呢？所以最小还得保证是宽的一半以上。

　　看代码吧。

 #include <bits/stdc++.h>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 using namespace std;

 const int N=;

 int main()

 {

     freopen("e://input.txt", "r", stdin);

     int n, m, x, y, ans;

     while(~scanf("%d%d%d%d",&n,&m,&x,&y))

     {

         if(n>m) swap(n,m),swap(x,y);//记得x和n是配套的。保证n<=m

         if(n==m && n& && x==y && x==(n+)/ )    //在正方形中央

             ans=x-;

         else        //长方形,不用管黑点在哪

         {

             int t=min( y, m-y+ );  //长：取小的一段

             int r=max( x-, n-x );  //宽：取长的一段。

             ans=min(t,r); //两种方式取短者

             ans=max(ans,  (n+)/ );  //绝对不允许少于宽的一半

         }

         printf("%d\n",ans);

     }

     return ;

 }

AC代码