题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5301
题面:
2 3 2 2 3 3 1 1
1 2HintCase 1 :You can split the floor into five 1×1 apartments. The answer is 1. Case 2:You can split the floor into three 2×1 apartments and two1×1 apartments. The answer is 2.If you want to split the floor into eight 1×1 apartments, it will be unacceptable because the apartment located on (2,2) can‘t have windows.
解题:
因为方格肯定是1*k的,这样才能让面积最小,一开始,看时限,以为是二分答案。但发现若没有坏点,那么答案就是ans=(min(n,m)+1)/2。但有坏点,会出现两种特殊情况。
1.n等于m,且n为奇数,同时坏点在中心点位置,那么答案就为ans-1;
2.(假设n>m)坏点所在的位置,形成的面向4条边框的距离中,总长为m-1的两条中的一条大于ans,且该条边所在位置,不能由上或下覆盖,那么就取三个方向上离该点(那条无法覆盖的边上离坏点最近的那个点)最近的距离为答案。
3.其余情况,答案都为ans不变。
总结:
其实,比赛的时候,以上两种特殊情况,都已经找到了,但是,思路太乱,造成不能理性得分析问题。这种问题,应该有条理地进行分析,讨论。想好了再去动手写。
代码:
#include <iostream> #include <cmath> using namespace std; int max(int a,int b) { return a>b?a:b; } int min(int a,int b) { return a<b?a:b; } int main() { int n,m,x,y,ans; while(cin>>n>>m>>x>>y) { ans=(min(n,m)+1)/2; if(n==m) { if(n%2) { if(x==(n+1)/2&&y==(m+1)/2) ans--; } } else { int le,ri,up,dw; if(n<m) { swap(n,m); swap(x,y); } le=y; ri=m-y+1; up=x; dw=n-x+1; if(m%2) { if(abs(le-ans)>1) { if(up>ans&&dw>ans) { ans=max(le-1,ri-1); ans=min(ans,up); ans=min(ans,dw); } } } else { if(!(le==ans||le==ans+1)) { if(up>ans&&dw>ans) { ans=max(le-1,ri-1); ans=min(ans,up); ans=min(ans,dw); } } } } cout<<ans<<endl; } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/david_jett/article/details/47054749