求助:被一个测试点数据卡住
查看原帖
求助:被一个测试点数据卡住
448502
JCLinux楼主2021/6/14 22:13

求救:一直被一个数据点卡住

#include<bits/stdc++.h>
using namespace std;
char arr[5002][5002];
int sum[5002][5002];
int main(){
	int n,m;
	cin >> n >> m;
	int max_x=0,max_y=0;
	for(int i=0;i<n;i++){
		int x,y,v;
		scanf("%d %d %d",&x,&y,&v);
		arr[x+1][y+1]=(char)v;
		//找出边界,不做额外的运算
		if(x+1>max_x) max_x=x+1;
		if(y+1>max_y) max_y=y+1;
	}
	//计算前缀和数组
	for(int x=1;x<=max_x;x++){
		for(int y=1;y<=max_y;y++){
			sum[x][y]=sum[x-1][y]+sum[x][y-1]-sum[x-1][y-1]+(int)arr[x][y];
		}
	}
	int MAX=0;
	//确定计算边界
	/*
	1:当m<=max_x&&m<=max_y时:从(m,m)到(max_x,max_y);
	2:当m<=max_x&&m>max_y时:从(m,max_y)到(max_x,max_y);
	3:当m>max_x&&m<=max_y时:从(max_x,m)到(max_x,max_y);
	4:当m>max_x&&m>max_y时:从(max_x,max_y)到(max_x,max_y);
	总结规律:从(min(m,max_x),min(m,max_y))到(max_x,max_y);
	从而保证计算的区域全部经过前缀和的计算,而且计算量最小
	*/
	for(int x=min(m,max_x);x<=max_x;x++){
		for(int y=min(m,max_y);y<=max_y;y++){
			//当覆盖的区域不足(m,m)时防止下标越界
			int a,b;
			a=x-m;b=y-m;
			if(a<0) a=0;
			if(b<0) b=0;
			int tmp=sum[x][y]-sum[a][y]-sum[x][b]+sum[a][b];
			if(tmp>MAX) MAX=tmp;
		}
	}
	cout <<MAX;
	return 0;
}

我想缩小范围,从而减小计算量,但是一直被那个数据点卡,希望大佬指出我这么做的问题在哪里,注释写在代码里,是我做这个题时候的思路。

2021/6/14 22:13
加载中...