基础算法题——十字阵列

约定不等于承诺〃 2023-07-06 08:59 34阅读 0赞

# 基础算法题——十字阵列 #

## 做题心得 ##

该算法题主要考查对算法复杂度的选择。  
题目意思简单易懂，但是如果选择复杂度过大的算法，就会导致在数据过大时，运行超时。  
这时我们应该考虑将算法复杂度降低。

## 十字阵列题目 ##

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
![示例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]  
[牛客网题目链接][Link 1]

## 题目分析 ##

题目中主要计算每个网格上的伤害值，然后每个网格伤害值相加得总伤害。  
按照我起初的思路：用一个二维数组列表格，计算每个网格中填入伤害值，然后再将每个网格伤害值相加。这样的思路没错，但是算法会太过复杂（仅用一个二维数组的算法代码在结尾）。于是我们选择有两个一维数组，一个二维数组，以空间的代价，去换取更高效的算法。

### 求出每个横坐标、纵坐标的z并分别放入N\[x\],M\[y\]数组中，为了排除重复加的情况再将横纵坐标组成的二维数组NM\[x\]\[y\]放入对应的z ###

为了更好让大家理解我说的意思，我就按示例1画出相应的模拟图  
在5 \* 5的表格中，x1=1，y1=1上施法，伤害为z1=1。  
（红色数字为伤害，黑色数字为序号）  
![模拟图1][1]  
在5\*5的表格中，x2=2，y2=2上施法，伤害为z2=2。  
![模拟图2][2]  
最终可得  
![最终图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 2]  
那么N\[1\]=z1=1 … N\[5\]=z5=5。M\[1\]=z1=1 … M\[5\]=5。  
NM\[1\]\[1\]=z1 … NM\[5\]\[5\]=z5。

题目所求每个网格中对应的wij\*(i+j)之和。  
我们可以通过两个一维数组与一个二维数组的组合，将每个网格对应的wij\*(i+j)求出，再通过嵌套循环将所有网格对应的wij\*(i+j)相加求余即可得出答案。

#### wij\*(i+j)=(N\[j\]+M\[i\]-NM\[j\]\[i\])\*(i+j) ####

最后附上算法代码：

#include<stdio.h>
    #define ll long long
    const ll mod=1000000007;
    int NM[2001][2001], N[2001], M[2001];
    int main()
    { 
    	ll n, m, h, i, j, sum, x, y, z, count,temp;
    
    	scanf("%lld%lld%lld", &n, &m, &h);
    	for(j=0; j<=n; j++)
    	for(i=0; i<=m; i++)
    	NM[j][i]=0;
    
    	for(count=1; count<=h; count++)
    	{ 
    		scanf("%lld%lld%lld", &x, &y, &z);
    		N[x]+=z;
    		M[y]+=z;
    		NM[x][y]+=z;
    	}
    	sum=0;
    	for(j=1; j<=n; j++)
    	{ 
    		for(i=1; i<=m; i++)
    		{ 
    			temp=((N[j]+M[i]-NM[j][i])*(i+j))%mod;
    			sum=(sum+temp)%mod;
    		}
    	}
    	printf("%lld", sum);
    	
    	return 0;
    }

//一个二维数组代码
    #include<stdio.h>
    #define ll long long
    const ll mod=1000000007;
    int NM[2001][2001];
    int main()
    { 
    	ll H, i, j, sum, x, y, z, count,temp;
    	int N, M;
    
    	scanf("%d%d%lld", &N, &M, &H);
    	for(j=0; j<=N; j++)
    	for(i=0; i<=M; i++)
    	NM[j][i]=0;
    
    	for(count=1; count<=H; count++)
    	{ 
    		scanf("%lld%lld%lld", &x, &y, &z);
    		for(j=1; j<=N; j++)
    		{ 
    			NM[j][y]+=z;
    			NM[j][y]%=mod;
    		}
    		for(i=1; i<=M; i++)
    		{ 
    			NM[x][i]+=z;
    			NM[j][y]%=mod;
    		}
    		NM[x][y]-=z;
    	}
    	sum=0;
    	for(j=1; j<=N; j++)
    	{ 
    		for(i=1; i<=M; i++)
    		{ 
    			temp=(NM[j][i]*(i+j))%mod;
    			sum=(sum+temp)%mod;
    		}
    	}
    	printf("%lld", sum);
    	
    	return 0;
    }

## 总结 ##

该算法题其实不难，但是它告诉了我们算法复杂度的重要性，这也许就是为什么我们用顺序、选择、分支这些简单结构就能完成所有算法题，但还要再继续学习其他更复杂的算法的原因吧。  
我是小郑，坚持学习，特立独行。如果大家有其他看法欢迎留言讨论，大家一起学习进步。

### 如果觉得该文章对你有用的话，可以给我一个大大的赞喔！！ ###

#### 老铁的赞是鼓励我写博客的最大动力~ ####

![被代码吃了][20200223150108617.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200217162804350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200217162929785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[Link 1]: https://ac.nowcoder.com/acm/contest/3007/F
[1]: https://img-blog.csdnimg.cn/20200217172220917.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20200217172155269.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200217165739750.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[20200223150108617.png]: https://img-blog.csdnimg.cn/20200223150108617.png