洛谷P1565 牛宫

洛谷P1565 牛宫

题目描述

AP 神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M 的矩形空地。

空地中每个格子都有自己的海拔高度。AP 想让他的宫殿的平均海拔在海平面之上（假设

海平面的高度是0，平均数都会算吧？）。而且，AP 希望他的宫殿尽量大，能够容纳更

多的人来膜拜他。请问AP 的宫殿最后会有多大？

输入输出格式

输入格式：

第一行为N 和M。之后N 行，每行M 个数，描述的空地的海拔。

输出格式：

输出一行,表示宫殿最大面积。

输入输出样例

输入样例：

3 2
4 0
-10 8
-2 -2

输出样例：

4

题意很简单，求最大子矩阵和，且该矩阵和大于等于0。

输入时顺便做前缀和，然后是用三重循环枚举矩阵的长和宽，分别是宽的起始到宽的结束和长。

当当前矩阵与上一个矩阵相加大于0时，可直接得到一个新的矩阵并更新答案；

所以这道题最终要解决的是如何处理当前矩阵与上一个矩阵相加小于0的情况。

易知每个矩阵都可被纵向分割为两个小矩阵，那么就可以用二分查找，看当前矩阵和上一个矩阵组成的新矩阵是否能被分割成这样两个矩阵：一个矩阵和小于0，另一个大于0；

如果可以找到，那么更新答案；

因为宽始终不变，所以还需记录下小于0的那个矩阵的长，再用新矩阵的长减去即可；

最后要注意每次记录下矩阵和小于0的值和该矩阵的长，用单调栈记录。

/*由于某些原因，我全开了long long*/
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,ans;
long long top,sta[222222];
long long s[222][222],area;
long long a[222][222],kn[222222],f2[222][222];
long long ef(long long x)//二分查找出当前矩阵所包含的最小的小于0的矩阵
{
     long long l=1,r=top,mid,ans1=-1;
     while(l<=r)
     {
        mid=(l+r)/2;
        if(sta[mid]<x)
        {
            r=mid-1;ans1=mid;
        }
        else l=mid+1;
     }
     return ans1;
}
int main()
{
   scanf("%lld%lld",&n,&m);
   for(long long i=1;i<=n;i++)
   for(long long j=1;j<=m;j++)
   {
      scanf("%lld",&a[i][j]);
      s[i][j]=a[i][j]+s[i][j-1];//前缀和
   }
   for(long long i=1;i<=m;i++)//枚举起始宽
   for(long long j=i;j<=m;j++)//枚举结束宽
   {
      area=0;
      sta[0]=0,top=0;
      for(long long k=1;k<=n;k++)//枚举长
      {
         area+=s[k][j]-s[k][i-1];
         if(area>0)  ans=max(ans,(j-i+1)*k);
         else
         {
             long long num=ef(area);//矩阵和
             if(num!=-1)  ans=max(ans,(j-i+1)*(k-kn[num]));
             //找到了新矩阵所包含的大于0的矩阵才更新
             if(area<sta[top]) 
             {
                sta[++top]=area;//记录area<0的值
                kn[top]=k;//同时记录该矩阵的长
             }
         }
      }
   }
   cout<<ans<<endl;
   return 0;
}