题目链接
https://atcoder.jp/contests/agc066/tasks/agc066_a
题目大意
给定一个 \(N \times N\) 的方阵 \(A_{i, j}\) 和一个正整数 \(d\)。每次可以花费 \(x\) 的代价将矩阵的某一个位置加上 \(x\) 或减去 \(x\)。请构造一种方案使得方阵中所有相邻位置的差的绝对值大于等于 \(d\)，且代价之和小于等于 \(\frac{1}{2}N^{2}d\)。
数据范围
- \(2\le N \le 500\)
- \(1\le d \le 1000\)
- \(-1000 \le A_{i, j} \le 1000\)
解题思路
先说结论：
- 将方阵黑白染色，然后将黑色的位置变为 \(\bmod 2d = 0\) 的最近的数，将白色的位置变为 \(\bmod 2d = d\) 的最近的数，假设代价此为 \(c_0\)。
- 将方阵黑白染色，然后将白色的位置变为 \(\bmod 2d = 0\) 的最近的数，将黑色的位置变为 \(\bmod 2d = d\) 的最近的数，假设代价此为 \(c_1\)。
则上述两种情况中必有一种满足条件。
证明：
由于上述构造中黑白相邻位置的差的绝对值至少为 \(d\)，所以满足第一个条件。
考虑第二个条件。假设把一个位置上的数变为 \(\bmod 2d = 0\) 的最近数的代价为 \(x\)，变为 \(\bmod 2d = d\) 的最近的数的代价为 \(y\)，那么一定有 \(x + y = d\)。这就意味着 \(c_0 + c_1 = N ^ {2} d\)，则 \(c_0\) 和 \(c_1\) 中必有一个小于等于 \(\frac{1}{2}N^{2}d\)。