首页 > 代码库 > bzoj4302 Hdu 5301 Buildings
bzoj4302 Hdu 5301 Buildings
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4302
【题解】
出自2015多校-学军
题意大概是给出一个n*m的格子有一个格子(x,y)是坏的,用一些矩形覆盖没有坏的格子,使得每个矩形都有一面靠着边界。求最大的矩形的面积最小。
稍微分析就会发现肯定是1*x的矩形最优,因为如果是2*x可以分成2个1*x。
那么我们先把矩形转转位置,使得n<=m,且(x,y)在左上角。
矩形内没有坏点,显然方案是(n+1)/2
我们画个图,黑色的那个是坏点,我们发现要处理坏点有2种方法
(其中红色的为处理坏点的,绿色的为正常的答案)
显然是这两种方案中选一个花费最小的。
答案就是max((n+1)/2, min(n-x,y))
有一种特殊情况需要特判就是:n=m,且坏点在正方形正中心,答案是x-1
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m, x, y, ans; int main() { while(~scanf("%d%d%d%d", &n, &m, &x, &y)) { if(n > m) swap(n, m), swap(x, y); x = min(x, n-x+1), y = min(y, m-y+1); if(n == m && (n&1) && x == (n+1)/2 && x == y) ans = x-1; else ans = max((n+1)/2, min(n-x, y)); printf("%d\n", ans); } return 0; }
bzoj4302 Hdu 5301 Buildings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。