盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5301 Buildings(数学, 想法)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5301

题意

有nm的矩形,其中在(x,y)位置有一个坏的11的矩形不能用,现在问要将该矩阵用其他小矩阵填满,且这些小矩阵至少要和大矩阵的四条边中的一条边有一些公共部分。现在要是这些小矩形中最大的面积最小,求该面积。

思路

首先如果没有坏的矩形,假设最后分得的矩形为ab,那么一定还可以继续分为1b或者1a的形式,答案一定为min(n + 1, m + 1)/2。
现在加入了一个坏的矩形,如下图所示:

其中up和down都不包括小矩形,而left和right都包括该小矩形。
假设不考虑坏矩形,答案应该为ans=(n+1)/2
考虑坏矩形,如果min(left, right) <= ans, 那么左半边或者右边边直接用n
min(left, right)划分,另一边则还按照原先的划分。
如果min(left,right) > ans,那么就应该用min(max(up, down), min(left, right))中的来划分。(这里还要注意如果up==down的话,最小值还是ans)
最后有一个trick:如果n==m && x == y && 2 * x + 1 == n 那么答案应该为 n/2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
int n, m, x, y;
int main () {
while(~scanf("%d%d%d%d", &n, &m, &x, &y)) {
if (n > m) swap(n, m), swap(x, y);
int t = (n + 1) / 2;
int up = x - 1;
int dw = n - x;
int lf = y;
int rg = m - y + 1;
if (min(lf, rg) > t && up != dw) t = min(max(up, dw), min(lf, rg));
if ((n == m) && (n % 2 == 1) && (x == y) && (x * 2 - 1 == n)) t = n / 2;
printf("%d\n", t);
}
return 0;
}

更新日志

  • 14246606 2015-07-29 21:59:37 Accepted 5301 15MS 1564K 625 B G++ SIO__Five