long

题目描述

AP神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。AP想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，AP希望他的宫殿尽量大，能够容纳更多的人来膜拜他。请问AP的宫殿最后会有多大？

输入输出

输入

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

输出

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

样例

样例输入

3 2

4 0

-10 8

-2 -2

样例输出

4

说明

数据范围

对于30%的数据，N,M≤50;

对于100%的数据，N,M≤200；

思路

用前缀和a[i][j]表示第i行1~j列的和
开一个单调栈，存海拔之和
a[k][j]-a[k][q]代表第k行第q列到第j列的海拔高度和
当s<0时，设s=p (p<0),在栈中寻找p所对应的f[p],
用当前行数k减去f[p]，即可得到一段平均海拔在海平面之上的区间。

代码

#include<cstdio>

#include<iostream>

using namespace std;

long long n,m,x,a[201][201],f[201],sta[201],size,ans;

inline long long erfen(long long u) {

	long long l=1,r=size,tot=-1;

	while(l<=r) {

		long long mid=(l+r)>>1;

		if(sta[mid]<u) {

			r=mid-1;

			tot=mid;

		} else l=mid+1;

	}

	return tot;

}

inline int read() {

	long long x=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

	return x*w;

}

int main() {

	freopen("long.in","r",stdin);

	freopen("long.out","w",stdout);

	n=read();

	m=read();

	for(long long i=1; i<=n; i++)

		for(long long j=1; j<=m; j++) {

			x=read();

			a[i][j]=a[i][j-1]+x;

		}

	for(long long i=1; i<=m; i++)

		for(long long j=1; j<=m; j++) {

			long long s=0;

			sta[0]=1e10;

			size=0;

			for(long long k=1; k<=n; k++) {

				s+=a[k][j]-a[k][i-1];

				if(s>0) ans=max(ans,k*(j-i+1));

				else {

					int z=erfen(s);

					if(z!=-1) ans=max(ans,(j-i+1)*(k-f[z]));

				}

				if(sta[size]>s) sta[++size]=s,f[size]=k;

			}

		}

	printf("%lld\n",ans);

	return 0;

}

巴特西

【单调栈】【前缀和】【二分查找】8.28题解-long

long

题目描述

输入输出

样例

说明

思路

代码

最新文章

热门文章