题目大意
牛牛和 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函数的实现，下面有两个方法：
- 从左到右依次枚举每一刀，找到一个最小的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;
}
- 观察上面的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(log2(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;
}
