[COCI2021-2022#6] Zemljište
题目描述
有一块地,大小为 $r \times s$,$\rm Matej$ 想买下它。这块地每个 $1\times1$ 的正方形都有不同的价格。
设一片非空子矩阵价格总和为 $m$,则这片子矩阵的权值为 $|m-a|+|m-b|$,您需要找到最小权值的子矩阵。
您只需要输出最小权值即可。
输入格式
第一行包含四个正整数 $r$, $s$ , $a$ 和 $b$ 。
下面 $r$ 行,第 $i$ 行,有 $s$ 个正整数,第 $j$ 个数表示 $c_{i,j}$,表示价格。
输出格式
一行一个整数 $v$,表示最小非空子矩阵的权值。
样例 #1
样例输入 #1
2 2 10 10
1 3
4 1
样例输出 #1
2
样例 #2
样例输入 #2
3 2 3 4
1 9
1 1
8 1
样例输出 #2
3
样例 #3
样例输入 #3
3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7
样例输出 #3
2
提示
样例解释 2
如图,总价格是$1 + 1 = 2$,这块地的权值是 $|3−2| + |4−2| =3$。
数据范围:
对于 $14\%$ 的数据:$1\le r,s\le20$
对于 $28\%$ 的数据:$1\le r,s\le100$
对于 $100\%$ 的数据:$1\le r,s\le500$,$1\le a,b,c_{i,j}\le10^9$
本题分值与 COCI 2021-2022#6 分值相同,满分 $70$ 分
解题思路
很明显最直接的做法是枚举处所有的子矩阵,然后通过前缀和算出子矩阵的和 $m$,从而得到 $|m-a| + |m-b|$,取所有情况的最小值即可。为此我们需要枚举左上角和右下角的坐标来确定子矩阵,所以时间复杂度为 $O(n^4)$,明显超时。
由于 $n$ 的最大取值是 $500$,所以应该要把时间复杂度控制在 $O(n^3)$ 级别,而 $O(n^3 \log{n})$ 大概率会超时因此不行。一般来说要枚举子矩阵都会想到枚举左上角 $(x_1,x_2)$ 和右下角 $(x_2, y_2)$,这里再提供另外一种思路,即枚举子矩阵的上边界 $x_1$,下边界 $x_2$,左边界 $y_1$,右边界 $y_2$。然而这样做时间复杂度还是 $O(n^4)$,由于要把复杂度控制在 $O(n^3)$,意味着我们只能枚举三个边界,另外一个边界通过 $O(1)$ 来得到。
不妨假设枚举上边界 $x_1$,下边界 $x_2$ 和右边界 $y_2$,这时左边界 $y_1$ 的选择就有 $y_1 \in [1, y_2]$,在这些选择中要确定使得 $|m-a| + |m-b|$ 最小的那个。这时我们就要观察 $|m-a| + |m-b|$ 这个式子了,很明显只有 $m$ 会影响式子的结果。不妨假设 $a < b$(否则交换 $a$ 和 $b$ 即可),当 $m \in [a, b]$ 时,结果能够取到最小值 $b-a$。否则如果 $m < a$,式子结果就是 $a + b - 2m$,因此要让 $m$ 尽可能接近 $a$(在 $m < a$ 的前提下),才能让结果尽可能小。同理,当 $m > b$,式子结果就是 $2m - a - b$,应该让 $m$ 尽可能接近 $b$ 结果才能变小。
另外由于矩阵中的元素均为正整数,因此随着 $y_1$ 往右移动子矩阵的和就会减小,因此满足单调性,可以二分出满足 $m \leq a$ 的最大的 $m$ 所对应的 $y_1$,假设为 $u$;二分出满足 $m \geq b$ 的最小的 $m$ 所对应的 $y_1$,假设为 $v$。那么就可以对这两个子矩阵 $(x_1, u, x_2, y_2)$ 和 $(x_1, v, x_2, y_2)$ 分别计算式子的结果取最小值。这种做法的时间复杂度是 $O(n^3 \log{n})$。
然而我们还需要优化到 $O(n^3)$。事实上随着 $y_2$ 往右移动,$u$ 和 $v$ 也最会往右移动。否则 $y_2$ 往右移动得到 $y_2'$,$u$ 会往左移动得到 $u'$,子矩阵 $(x_1, u', x_2, y_2')$ 的和满足不超过 $a$ 的最大值,意味着子矩阵 $(x_1, u', x_2, y_2)$ 的和也不超过 $a$,且比子矩阵 $(x_1, u, x_2, y_2)$ 的和更接近 $a$,这就与之前的假设矛盾了。同理分析 $v$。因此这里我们可以用双指针来优化。
AC 代码如下,时间复杂度为 $O(n^3)$:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510;
LL s[N][N];
LL get(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
int main() {
int n, m, a, b;
scanf("%d %d %d %d", &n, &m, &a, &b);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%lld", &s[i][j]);
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
LL ret = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
for (int k = 1, u = 1, v = 1; k <= m; k++) {
while (u < k && get(i, u, j, k) > a) {
u++;
}
LL t = get(i, u, j, k);
ret = min(ret, abs(t - a) + abs(t - b));
while (v < k && get(i, v + 1, j, k) >= b) {
v++;
}
t = get(i, v, j, k);
ret = min(ret, abs(t - a) + abs(t - b));
}
}
}
printf("%lld", ret);
return 0;
}
参考资料
P8343 题解:https://www.luogu.com.cn/blog/xiaolu12356/solution-p8343
标签:COCI2021,边界,int,矩阵,复杂度,样例,权值,Zemlji,te From: https://www.cnblogs.com/onlyblues/p/17776269.html