题意:给出一个由很多格子组成的矩形的宽高(2H,W105),然后将其分成三个矩形,求最大的矩形和最小的矩形最小的差值。


题解:分成三个矩形只有四种情况,三份横着切,三份竖着切;一份横,两份竖着,一份竖着,两份横着。但是我们要是将宽高转换一下其实就两种情况。然后需要注意的就是一二开的情况,直接取中间剖分有可能不能得到最小的差值,还要往左右挪一挪才能得到最优解。


代码:

#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
 
typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=105;
 
LL one(LL x, LL y){
   LL tmp=inf, a, b, c;
   if(x>=3){
       c=x%3;
       a=(x-c)/3;
       if(c==0){
           return 0;
       }
       else if(c==1){
           a++;b=(x-a)/2;
       }
       else if(c==2){
           a++;b=x-a*2;
       }
       tmp=min(tmp, abs(a*y-b*y));
   }
   return tmp;
}
 
LL two(LL x, LL y){
   LL tmp=inf, a, b, c, d, mx, mn;
   a=x/2;
   b=x-a;
   c=y/2;
   d=y-c;
   mx=max(max(a*y, b*c), b*d);
   mn=min(min(a*y, b*c), b*d);
   while(a&&mx-mn<tmp){
       tmp=mx-mn;
       a--;
       b++;
       mx=max(max(a*y, b*c), b*d);
       mn=min(min(a*y, b*c), b*d);
   }
   return tmp;
}
 
int main()
{
   int x, y;
   while(~scanf("%d%d", &x, &y)){
       LL ans=inf;
       ans=min(ans, one(x, y));
       ans=min(ans, one(y, x));
       ans=min(ans, two(x, y));
       ans=min(ans, two(y, x));
       printf("%lld\n", ans);
   }
   return 0;
}