HDU 5301 Buildings(2015多校联合)

发表于   |  

题目链接：

戳我

题目大意：

$n*m$列的矩阵，删除一个格子$x,y$。用矩形来填充矩阵。且矩形至少有一边是在矩阵的边缘上。求满足条件的矩形填充方式中面积最大的矩形，要使得该最大矩形的面积最小。

样例分析：

见题

解题思路：

任何矩形都可以分为宽度为1的小矩形，所以只考虑矩形的可以的最小长度即可。

讨论：
$m$ 代表行，$n$ 代表列
输入的时候先输入行，在输入列，当行比列大的时候要交换
任何矩形都可以分为宽度为1的小矩形，所以只考虑矩形的可以的最小长度即可。宽度始终为 $1$
当没有删除格子时，最小的面积是 $ans = min((n+1)/2,(m+1)/2)$
当 x，y处于矩形正中央时 ans- 1即可
其他情况：

如果m > n swap(n,m), swap(x,y)
之后如图所示，上下取大的 e，左右取小的f
面积就应该为 ans2 = min(e, f)
如果这个 ans2 比 最小面积ans小，肯定输入ans
否则就是 ans2

此处输入图片的描述

代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;

inline int mymin(int x, int y)
{
    return x < y ? x : y;
}
inline int mymax(int x, int y)
{
    return x > y ? x : y;
}

int main()
{
    //freopen("Mul2/data/data1002/b.in", "r", stdin);
    //freopen("2.out", "w", stdout);
    int n, m, x, y;
    int le, ri, up, down;
    int e, f, g;
    int ans = 0;
    while(~scanf("%d %d %d %d", &m, &n, &x, &y))
    {
        if(m > n)//n为长边,m为短边
        {
            swap(n, m); swap(x, y);
        }
        le = y - 1;//删除的格子距左端的距离 
        ri = n - y; //删除的格子距右端的距离 
        e = mymin(le, ri);

        up = x - 1; //删除的格子距上端的距离 
        down = m - x;//删除的格子距下端的距离 
        f = mymax(up, down);

        g = mymin(e+1, f);
        ans = (m+1) / 2;//没有删除格子时，最小的面积
        if(le == ri && ri == up && up== down)//如果n，m为奇数，且删除的格子在正中间
        {
            printf("%d\n", le);
        }
        else
        {
            printf("%d\n", mymax(ans, mymin(e+1, f)));
        }
    }
    return 0;
}