Skip to content

1378: 南水北调,东水西送

题目

题目描述

2051年注定是一个不平凡的年份,干旱、洪涝等气象灾害频发,人民的生命与财产安全受到了极大损失。兹年,中国东南部地区普降大雨,以秦岭淮河以南最为明显,蓄水充沛颇有洪泛趋势;西北部地区则遭受了严重的干旱灾害,数月无雨。

2051年的中国已经建成了 $n$ ​纵 $n$ ​​​横的网格形互联互通的水库网络,“南水北调,东水西送”的梦想已然成为现实,人民的幸福美好生活终于不再受到涝旱灾害的影响。一方有难,八方支援,党中央第一时间做出决策部署,东南部蓄水最多的水库立刻向西北部蓄水最少的水库输水,保障生产生活的正常运行。

可以认为水库网络是一个 $n \times n$ ​​​的矩阵,用正整数表示蓄水量。按上北下南左西右东分布,即最西北部的水库位于矩阵的左上角,最东南的水库位于矩阵右下角。我们需要找到储水量相对差距最大的两个水库进行输水,储水量少的那个水库必须严格相对在西北,储水量多的那个水库必须严格相对在东南(即两座水库的横、纵坐标均不能相等)。输水结束后,两水库储水量将保持一致。请你输出这一输水过程的输水量。

在党和人民的共同奋斗下,全国上下团结齐心,我们一定能打赢这场输水攻坚战!

输入格式

第一行一个整数 $n$​​ ,表示代表水库矩阵的长与宽。

接下来的 $n$​​ ​行,每行 $n$​​ 个正整数代表水库蓄水量。保证每个水库的储水量均为偶数。

输出格式

一个正整数 $x$​​​​,代表输水量。

样例输入

样例输入 1

text 3 2 4 6 8 10 12 14 16 18

样例输入 2

text 4 18 10 14 26 8 10 2 22 14 24 24 20 12 2 4 6

样例输出

样例输出 1

text 8

样例输出 2

text 9

数据范围

  • 对于50%的数据,$1\leq n\leq 20$​。

  • 对于100%的数据,$1\leq n\leq 2 \times10^3$​​, $1 \leq 水库蓄水量 \leq 10^6$​​。保证$x>0$​​​​​。

  • 取两个数的最小(大)值可以这么写:

c++ int a = 2; int b = 3; int maxx = max(a, b); int minn = min(a, b);

  • hint:想一想小作业1307数方块是怎么做的?(不允许翻阅OJ上自己曾经提交的代码,违者按作弊处理)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!