分割矩阵 (二分范围[L,R)）

分割矩阵
                   (browine.c/cpp/pas)
【问题描述】
    有N*M的一个非负整数矩阵。现在要把矩阵分成A*B块。矩阵先水平地切A-1刀，把矩阵划分成A块。然后再把剩下来的每一块独立地切竖着B-1刀。每块的价值为块上的数字和。求一种方案，使得最小价值块的价值最大。
【输入格式】
    第一行四个整数N,M,A,B。
    接下来N行，每行M个非负整数。代表这个矩阵
【输出格式】
    一个数字。最小价值块的价值。
【样例输入】
5 4 4 2
1 2 21
3 1 1 1
2 0 1 3
1 1 1 1
1 1 11
【样例输出】
    3

样例解释见图片
【数据规模】
   1<=A<=N<=500
   1<=B<=M<=500
    其他数字小于4000。

二分的同志请注意了
m=(l+r)/2 <-----这句是永远也枚不到L与R的

[cpp]
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (500+10)
#define MAXM (500+10)
#define MAXT (2000000+10)
int n,m,t1,t2,a[MAXN][MAXM],sum[MAXN][MAXM]={0};
bool is_ok(int l,int r,int _m)
{
    int tot=0,p=0;
    for (int i=1;i<=m;i++)
    {
        tot+=sum[r][i]-sum[l-1][i];
        if (tot>=_m) {tot=0;p++;}
    }
    if (p>=t2) return 1;
    else return 0;
}
bool is_ok_(int _m)
{
    int p=0,l=1;
    for (int i=1;i<=n;i++)
    {
        if (is_ok(l,i,_m)) {l=i+1;p++;}
    }
    if (p>=t1) return 1;
    else return 0;
}
int main()
{
    freopen("browine.in","r",stdin);
    freopen("browine.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&t1,&t2);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            sum[i][j]=sum[i-1][j]+a[i][j];
        }
    /*
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            printf("%d ",sum[i][j]);
        }
    */
// cout<<(is_ok_(4));
    int l=1,r=1,ans=0;
    for (int j=1;j<=m;j++) r+=sum[n][j];

    for (int i=1;i<=60;i++)
    {
        int m_=(l+r)/2;
        if (is_ok_(m_)) {l=ans=m_;}
        else r=m_;
    }
    printf("%d\n",ans);

// while (1);
    return 0;
}

补充：软件开发 , C++ ,