題意
https://vjudge.net/problem/AtCoder-2565
將一個H*W的矩形切成三份，每一次只能水平或者垂直切，問最大塊的面積-最小快的面積 的最小值是多少，
思路
先列舉水平切第一塊的高i，那么剩余部分h-i要么繼續水平切、要么垂直切，因為要使最大快-最小快 最小，那么剩下的兩塊肯定是相差最少為好，所以可以拆成w/2和w-w/2兩塊，也可以拆成（h-i）/2和（h-i）-（h-i）/2，
再列舉垂直切的第一塊的寬度，后續操作類似，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int main()
{
std::ios::sync_with_stdio(false);
ll h,w;
while(cin>>h>>w)
{
ll ans=inf;
for(int i=1;i<h;i++)
{
ll a=h-i;
if(i!=h-1)
{
ans=min(ans,max(i*w,max(a/2*w,(a-a/2)*w))-min(i*w,min(a/2*w,(a-a/2)*w)));
}
ans=min(ans,max(i*w,max(a*(w/2),a*(w-w/2)))-min(i*w,min(a*(w/2),a*(w-w/2))));
// cout<<i<<" "<<max(i*w,max(a*(w/2),a*(w-w/2)))-min(i*w,min(a*(w/2),a*(w-w/2)))<<" "<<ans<<endl;
// cout<<a<<" "<<i<<" "<<w<<" "<<endl;
}
// cout<<ans<<endl;
for(int i=1;i<w;i++)
{
ll a=w-i;
if(i!=w-1)
{
ans=min(ans,max(i*h,max(a/2*h,(a-a/2)*h))-min(i*h,min(a/2*h,(a-a/2)*h)));
}
ans=min(ans,max(i*h,max(a*(h/2),a*(h-h/2)))-min(i*h,min(a*(h/2),a*(h-h/2))));
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/125566.html
標籤：其他