首页 > ACM题库 > 九度OJ > 九度-1102-最小面积子矩阵[解题代码]
2013
12-12

九度-1102-最小面积子矩阵[解题代码]

题目来源:2010年上海交通大学计算机研究生机试真题

题目描述:

一个N*M的矩阵,找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵(矩阵中元素个数为矩阵面积)

输入:

每个案例第一行三个正整数N,M<=100,表示矩阵大小,和一个整数K
接下来N行,每行M个数,表示矩阵每个元素的值

输出:

输出最小面积的值。如果出现任意矩阵的和都小于K,直接输出-1。

样例输入:
4 4 10
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
样例输出:
1

cpp 代码如下:
#include <stdio.h>
#include <cstring>
int sum[101][101];
int res[101];
int mat[101][101];
int  m,n,k;
bool check(int len)
{
    int i;
    for(i=1;i+len-1<=m;i++)
        if(res[i+len-1]-res[i-1]>=k)
            return true;
        return false;
}
int main()
{
    int i,j,ans,lf,rt,mid,len;
    while (scanf("%d %d %d", &n, &m, &k) != EOF)
    {
        memset(sum,0,101*sizeof(int));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&mat[i][j]);
                sum[i][j]=sum[i-1][j]+mat[i][j];
            }
            ans=-1;
            for(len=1;len<=n;len++)
            {
                for(i=1;i+len-1<=n;i++)
                {
                    res[0]=0;
                    for(j=1;j<=m;j++)
                        res[j]=res[j-1]-sum[i-1][j]+sum[i+len-1][j];
                    if(res[m]<k) continue;
                    lf=1;rt=m+1;
                    while(lf<rt)
                    {
                        mid=(lf+rt)>>1;
                        if(ans!=-1&&len*mid>ans)
                        {
                            rt=mid;
                            continue;
                        }
                        if(check(mid))
                        {
                            if(mid*len<ans||ans==-1)
                                ans=mid*len;
                            rt=mid;
                        }
                        else lf=mid+1;
                    }
                }
            }
            printf("%d\n",ans);
    }
    return 0;
}
/**************************************************************
	Problem: 1102
	User: coder
	Language: C++
	Result: Accepted
	Time:10 ms
	Memory:1100 kb
****************************************************************/


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮