c++解修剪花圃问题

C++解“修剪花圃”

题目描述
你知道吗？在外国，如果你不修剪你的花圃，是要被贴罚单的。Xman忙于战斗，被贴了好多罚单。这一次好不容易休息了，他决定修剪一下。修剪成什么样子呢？当然是X形。
Xman的花圃是一个n*n的正方形，其中n为大于等于3的正奇数。在每个位置上都有几个植物，对应的正整数是该植物的高度h。Xman的修剪策略是，首先把不在两条对角线上的植物通通铲光，然后在对角线上找到最矮的一株植物，把剩余的其他植物都裁剪成与它等高，这样一个漂亮整齐的X型就出来了。
Xman的东西当然值钱了。每1单位高度的植物，就可以卖2美元，把减掉的植物都卖掉，就可以弥补罚单的损失了。你帮Xman计算一下一共可以卖多少钱。

输入
有多行。第一行是一个整数n（n<1000），表示花圃的边长。
接下来n行是一个n*n的正整数二维数组，每个正整数值表示对应植物的高度h（h<1000）。

输出
卖出的美元总数。

样例输入
3
1 1 3
3 2 2
1 2 2
样例输出
24

关于本题的解法可以通过数组来进行求解：

for (i = 0; i < n; i++)//n是第一行输入的数据。
	for (j = 0; j < n; j++)
		cin >> a[i][j];//通过两次循环来给数组以此赋值。

那么如何来进行花圃的判断呢？
已知花圃修剪时呈“X”型，所以在此位置的行列关系分析可得：

(i == j) || (i + j == n - 1)

通过以上两点即可进行判断。

故本题解法如下所示：

#include<iostream>
using namespace std;
int a[1000][1000], n, i, j, m, s;//将数组a放在全局变量里面定义，否则会出现自动结束的情况。
int main()
{
	s = 0;  
	m = 1000;//m存在的意义为找出数组中的最小值，故在初始时将其赋值范围中的最大值参与后续的判断。
	cin >> n;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			cin >> a[i][j];
			if ((i == j) || (i + j == n - 1))
			{
				if (a[i][j] < m)
					m = a[i][j];//m为数组中的最小值
			}
			else
			{
				s = s + a[i][j];//全部剪去
			}

		}
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if ((i == j) || (i + j == n - 1))
				s = s + (a[i][j] - m);
		}
	}
	cout << s * 2;
	return 0;
}

本题的难点在于全局变量的考虑以及修剪出特殊形状时 i 、j 之间关系的判断。

以上，希望对您的解题有所帮助。