Test 3.27 T3 矩阵

Description

给一个 n*n 的地图,每个格子有一个价格,找一个矩形区域,使其价格总和位于[k,2k]

Input

输入 k n(n<2000)和一个 n*n 的地图

Output

输出矩形的左上和右下的列-行坐标或 NIE

Sample Input #1

4 3

1 1 1

1 9 1

1 1 1

Sample Output #1

NIE

Sample Input #2

8 4

1 2 1 3

25 1 2 1

4 20 3 3

3 30 12 2

Sample Output #2

2 1 4 2

Solution

有种情况十分显然：当矩阵内有一个的值大于等于k且小于等于2k时可直接输出该点的坐标。否则，说明矩阵中的点分为两类：一是小于k的，一是大于2k的。另外，对于任何一个值大于2k的点，我们都不会去选他。所以我们可以找一个子矩阵使其内的所有值都小于k，那么只要矩阵的权值和大于k，就一定可以通过删去行和列使其和在区间[k,2k]之内。这样就把问题转化为在一个矩形中寻找极大子矩阵的问题，可以通过单调栈来实现。

每到一格时，就更新以这一格为终点的在这一列i中的最长的连续一段值均小于k(称为极大区间)的长度a[i]。扫完一行后，让每个点一次入栈，维护其a[i]的单调递增。这样能够保证第s[top]列到第s[top-1]+1列的极大区间长均不小于s[top]。每次弹出栈顶元素时都在以(j-s[top]+1,s[top]-1)为左上角、以(j,i-1)为右下角的子矩阵中寻找答案。如果该矩阵的第一行的和大于k，就删去第一行，否则删去最后一行。当两行重合时，就开始删列。只要统计到可行答案就输出并结束程序。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 2010

using namespace std;

int a[N];

bool mp[N][N];

long long pre[N][N];

void YES(int A,int B,int C,int D)

{

    printf("%d %d %d %d",A,B,C,D);

    exit(0);

}

int s[N],t;

long long cal(int A,int B,int C,int D)

{

    return pre[C][D]-pre[A-1][D]-pre[C][B-1]+pre[A-1][B-1];

}

int K,n;

void cut(int A,int B,int C,int D)

{

	while(cal(A,B,C,D)>2*K)

	{

		if(A==C) D--;

		else if(cal(A+1,B,C,D)>=K) A++;

		else C--;

	}

	YES(B,A,D,C);

}

int main()

{

	scanf("%d%d",&K,&n);

	int i,j,x,y;

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

	for(j=1;j<=n;j++)

	{

		scanf("%d",&x);

		if(x>=K&&x<=2*K) YES(j,i,j,i);

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

		mp[i][j]=(x<K);

	}

	for(j=1;j<=n;j++)

	{

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

		a[i]=mp[j][i]?a[i]+1:0;

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

		{

			while(t&&a[s[t]]>=a[i])

			{

				if(cal(j-a[s[t]]+1,s[t-1]+1,j,i-1)>=K) cut(j-a[s[t]]+1,s[t-1]+1,j,i-1);

				t--;

			}

			t++;s[t]=i;

		}

		while(t)

		{

			if(cal(j-a[s[t]]+1,s[t-1]+1,j,n)>=K) cut(j-a[s[t]]+1,s[t-1]+1,j,n);

			t--;

		}

	}

	puts("NIE");

    return 0;

}

巴特西