牛客-分田地

发表于 | 分类于 ，

题目

描述

牛牛和 15 个朋友来玩打土豪分田地的游戏，
牛牛决定让你来分田地，
地主的田地可以看成是一个矩形，每个位置有一个价值。
分割田地的方法是横竖各切三刀，分成 16 份，
作为领导干部，牛牛总是会选择其中总价值最小的一份田地， 
作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，
你知道这个值最大可以是多少吗？

输入

每个输入包含 1 个测试用例。
每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 75），表示田地的大小，
接下来的 n 行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。

输出

输出一行表示牛牛所能取得的最大的价值

Example

Input

4 4
3332
3233
3332
2323

Output

2

题解

二分法

  • 定义数组 soil[i][j] 为第 0-i 行,0-j 列范围内的土地的总价值,
  • 所以可以获得的最高价值 ans 一定在 (0,soil[n][m]) 内,
  • 二分区间,判断中间值 mid 是否小于等于某一种分法中的最小价值,并进行二分区间变换
  • 若是更新 ans
  • 判断是否是最小值的方法是
    • 遍历所有横切 3 刀的情况
      • 纵切第 1 刀若判断是否是此列的最小值,
      • 若是切下一刀,
      • 若不是后移这一刀,继续判断
      • 若始终无法纵向切下一刀,则继续遍历横向切法
      • 若对于纵切 3 刀,形成的 4 列,mid 都满足价值最小的条件,返回 true
    • 若所有情况都不满足,返回 false
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
#include<bits/stdc++.h>

using namespace std;

int soil[76][76],m,n;

int getSum(int x1,int y1,int x2,int y2)
{
    return soil[x2][y2]-soil[x2][y1]-soil[x1][y2]+soil[x1][y1];
}

bool isMin(int num)
{
    for(int i=1;i<n-2;++i)
        for(int j=i+1;j<n-1;++j)
            for(int k=j+1,cnt=0,pre=0;k<n;++k,cnt=0,pre=0)
                for(int l=1;l<=m;++l)
                    if(getSum(0,pre,i,l)>=num&&
                       getSum(i,pre,j,l)>=num&&
                       getSum(j,pre,k,l)>=num&&
                       getSum(k,pre,m,l)>=num)
                    {
                        if((++cnt)==4)return 1;
                        pre=l;
                    }
    return 0;
}

int main()
{
    char c;
    while(cin>>m>>n)
    {
        memset(soil,0,sizeof soil);
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
            {
                cin>>c;
                soil[i][j]=soil[i-1][j]+soil[i][j-1]-soil[i-1][j-1]+c-'0';
            }
        int l=0,r=soil[m][n],mid,ans;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(isMin(mid))
                l=mid+1,ans=mid;
            else
                r=mid-1;
        }
        cout<<ans<<endl;
    }
}