OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2007】理想的正方形

【题目描述】

有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

【输入】

第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

【输出】

仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

【输入样例】

5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2

【输出样例】

1

【数据范围】

(1)矩阵中的所有数都不超过1,000,000,000
(2)20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
(3)100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100

【题解】

问题要求求出一个确定大小且不变的正方形内的最大最小值,所以考虑用单调队列优化。但问题是二维的,需要稍加改进。

首先用单调队列维护出每一行里,以每个数为最右端、长度为n的一段中的最大最小值,记作max1,min1。再用单调队列维护出max1(min1)的每一列里,以每个数为最下端,长度为n的一段中的最大(最小)值,记作max2(min2)。现在max2,min2即表示以每个格子为右下角,一个n*n的正方形里的最大最小值,再枚举一次得到答案。

【代码】

两次单调队列维护和最后的枚举都是O(ab)完成。

http://paste.ubuntu.com/8118459/

评论

© OI技术宅 | Powered by LOFTER