暴力美学 枚举+二分答案 [分田地-2017网易内推]

题目大意

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

输入描述:

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

输出描述:

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

示例1

输入

4 4
3332
3233
3332
2323

输出

2

分析

题目的任务是在一个矩阵上横切3刀，竖切3刀，直接暴力枚举的话复杂度是n^6。实际上题目要求的是使最小值最大，故可以二分答案。

常见的方法是二分答案x，先枚举横切三刀的位置，假设为R1，R2，R3。接下来是判断能否通过竖切3刀，使得16块区域的和都不小于x。这一部分的代码如下：

void work()
{
    int ans = 0;
    for(R1=1;R1<n;R1++)
        for(R2=R1+1;R2<n;R2++)
            for(R3=R2+1;R3<n;R3++)
            {
                int l = 0,r=1e9, mid;
                while(l+1<r)
                {
                    mid=(l+r)>>1;
                    if(ok1(mid))
                        l=mid;
                    else
                        r=mid;
                }
                if(l>ans) ans = l;
            }
    cout << ans;
}

关键在于上面的ok函数的实现，下面有两个方法：

1. 从左到右依次枚举每一刀，找到一个最小的i，使得左边的四个子矩阵的和都不小于x，最终判定能不能连续切4次即可，复杂度O(n)。代码如下：

bool ok1(int x)
{
    int T = 0,i,start = 0;
    for(i=1;i<=n;i++)
    {
        if(sum(0,start,R1,i)>=x&&sum(R1,start,R2,i)>=x&&sum(R2,start,R3,i)>=x&&sum(R3,start,n,i)>=x)
        {
            T++;
            start = i;
            if(T==4) break;
        }
    }
    return T == 4;
}

2. 观察上面的sum()函数，容易发现每一刀切下后，其变化都是单调不降的。因此可以再次使用二分来找到这个i，进一步降低时间复杂度为O(klogn)：

bool ok(int x)
{
    int T = 4,l,r=0,mid,start;
    while(T--)
    {
        start = r; l = r; r = m+1;
        while(l<r)
        {
            mid = (l+r)>>1;
            if(sum(0,start,R1,mid)>=x&&sum(R1,start,R2,mid)>=x&&sum(R2,start,R3,mid)>=x&&sum(R3,start,n,mid)>=x)
                r=mid;
            else
                l=mid+1;
        }
        if(r==m+1) return 0;
    }
    return 1;
}

总结

1、通过二分嵌套，算法复杂度为枚举O(n^3)O(log^2(n))=O(n3log^2(n))*
2、注意到两次二分的写法，外层二分是求满足条件的最大值，而内层二分求的是满足条件的最小值。
3、暴力美学，利用二分减少计算量。

完整代码如下

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<string>
#include<stack>
#include<set>
#define mem(f) memset(f,0,sizeof(f))
#define P2 pair<LL,LL>
typedef long long LL;
using namespace std;
const LL MOD = 1e9+7;
const int N = 85;
int n,m,R1,R2,R3;
string g[N];
int s[N][N];
void init()
{
    int i,j;
    for(i=0;i<n;i++)
        cin >> g[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            s[i][j]=g[i-1][j-1]-48+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
inline int sum(int x1,int y1,int x2,int y2)
{
    return s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1];
}
  
bool ok(int x)
{
    int T = 4,l,r=0,mid,start;
    while(T--)
    {
        start = r; l = r; r = m+1;
        while(l<r)
        {
            mid = (l+r)>>1;
  
            if(sum(0,start,R1,mid)>=x&&sum(R1,start,R2,mid)>=x&&sum(R2,start,R3,mid)>=x&&sum(R3,start,n,mid)>=x)
                r=mid;
            else
                l=mid+1;
        }
        if(r==m+1) return 0;
    }
    return 1;
}
  
void work()
{
    int ans = 0;
    for(R1=1;R1<n;R1++)
        for(R2=R1+1;R2<n;R2++)
            for(R3=R2+1;R3<n;R3++)
            {
                int l = 0,r=1e9, mid;
                while(l+1<r)
                {
                    mid=(l+r)/2;
                    if(ok(mid))
                        l=mid;
                    else
                        r=mid;
                }
                if(l>ans) ans = l;
            }
    cout << ans;
}
  
int main()
{
    while(cin >> n >> m)
    {
        //cin >> A >> B;
        init();
        work();
    }
  
    return 0;
}