2015 Multi-University Training Contest 2 1002 Buildings
Buildings
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5301
Mean:
n*m列的网格,删除一个格子x,y,用矩形来填充矩阵。且矩形至少有一边是在矩阵的边缘上。
要使最大矩形的面积最小,求满足条件的矩形填充方式中面积最大的矩形。
analyse:
任何矩形都可以分为宽度为1的小矩形,所以只考虑矩形的可以的最小长度即可。
讨论:
不删除格子时:最小长度为min((n+1)/2,(m+1)/2) = len
n = m:
n为奇数,且当x,y在正中心的时候,len- 1即可
其他条件len不变 , 显然成立。
n != m:
如果n > m swap(n,m), swap(x,y)
由于对称性,把矩阵分为四块,把x,y变换到矩阵的右上角。
可以知道 删除点后len只能变大不能变小。
且即使增大不会大于 (m+1)/2。
x
如图:x下方的3必须被矩形覆盖,那么长度 为 min(1 到3的长度,2到3的长度)
然后取min((m+1)/2, max(len,min(1-->3,2-->3)))即可。
Time complexity: O(N)
Source code:
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-23-18.23
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int main()
{
ios_base::sync_with_stdio( false );
cin.tie( );
int n, m, x, y;
while( cin >> n >> m >> x >> y )
{
int max1, max2, max3, max4, maxn;
max1 = max2 = max3 = max4 = maxn = ;
max1 = min( min( n - x + , x ), m - y );
max2 = min( min( n - x + , x ), y - );
max3 = min( min( m - y + , y ), n - x );
max4 = min( min( m - y + , y ), x - );
maxn = max( max( max1, max2 ), max( max3, max4 ) );
// if(n<m) swap(n,m),swap(x,y);
// maxn=min(max(x-1,n-x), min(m-y+1,y));
if( ( m == n ) && ( m % == ) )
{
if( ( x == y ) && x == ( ( m + ) / ) )
{
cout << m / << endl;
continue;
}
cout << max( maxn, ( m + ) / ) << endl;
continue;
}
int minn = min( n, m );
cout << max( maxn, ( minn + ) / ) << endl;
}
return ;
}
/*
*/
最新文章
- 【Android】实现XML解析的几种技术
- string.Format格式化
- brew安装
- 拾遗:『Linux Capability』
- 网站不能访问(httperrLog【Timer_MinBytesPerSecond】【Timer_ConnectionIdle】)(转载)
- Java内存管理:深入Java内存区域
- jQuery包裹节点用法完整示例
- UIview lianxi
- 三个重要的游标sp_cursoropen
- C++第三课:类的使用(一)[个人见解]
- 002-MVC布局页
- 考研计算机复试(广东工业大学C语言复试2014~2017笔试题)(精华题选)
- Ubuntu16.04 git上网速度慢的解决方法.
- Python基础-python流程控制之循环结构(五)
- jquery轻量级数字动画插件jquery.countup.js
- Week2 代码复查
- eclipse中可以导入其它工具编写的RobotFramework脚本吗?
- IDEA 2017的插件mybatis plugin
- Android studio 创建安卓项目hello
- (转)netty、mina性能对比分析