平衡 - 题解

标签与难度

标签: 二分答案, 图论, 优先队列, 贪心, 网格图, 广度优先搜索难度: 2100

题目大意喵~

你好呀，未来的算法大师！我是你的我助手，今天我们要解决一个关于大陆平衡的有趣问题，喵~

在一个 n x m 的网格世界里，有些地方是陆地，住着一定数量的人口；有些地方是湖泊，用 -1 表示。我们的目标是让整个大陆变得更加“和谐”，也就是让任意两块相邻的陆地，它们的人口数量差距尽可能小。

这里的“相邻”有点特别哦，不是上下左右四方向，而是包括了斜对角的六个方向：一个格子的邻居是它的左、右、上、下、左下、右上这六个格子。

我们扮演的是一位拥有神力的守护神，可以使用一种能力：将任意一块陆地的人口数量加一。但是神力不是无限的，我们最多只能使用 k 次。

那么问题来了：在最多使用 k 次神力的情况下，我们能达到的**最小的“不平衡值”**是多少呢？（“不平衡值”就是所有相邻陆地人口差的最大值）

简单来说，就是用不超过 k 的总代价，去升级人口，使得相邻人口的最大差值最小。是不是很有趣，呐？

解题思路分析

这道题的目标是“最小化一个最大值”（最小化不平衡值），一看到这种问法，我的雷达就响了！这通常是一个强烈的信号，提示我们可以使用二分答案的策略，喵~

1. 二分答案的框架

我们可以二分最终的答案，也就是那个“最小的不平衡值”。假设我们猜一个不平衡值 mid。现在问题就转化成了一个判定性问题：

check(mid)：我们是否能通过总共不超过 k 次的人口增加操作，使得所有相邻陆地的人口差的绝对值都不超过 mid？

如果 check(mid) 返回 true，说明 mid 这个不平衡值是可能达成的（或者可以达成一个比 mid 更小的值）。那么我们就可以尝试一个更小的答案，所以我们把二分范围的右边界缩小 r = mid。如果 check(mid) 返回 false，说明 mid 太小了，我们无论如何都无法在 k 次操作内达成，必须放宽要求，所以我们把左边界扩大 l = mid + 1。

这样，我们就可以通过二分法，高效地找到那个最小的可行的 mid 啦！

2. 如何实现 `check(mid)`

现在，核心问题变成了如何实现 check(mid) 函数。

对于任意两个相邻的陆地 A 和 B，其人口分别为 pop(A) 和 pop(B)。我们需要满足 |pop(A) - pop(B)| <= mid。因为我们只能增加人口，不能减少。所以：

如果 pop(A) > pop(B)，为了满足条件，我们需要确保 pop(A) - pop(B) <= mid。如果当前不满足，即 pop(A) - pop(B) > mid，我们别无选择，只能增加 pop(B)。
如果 pop(B) > pop(A)，同理，我们可能需要增加 pop(A)。

为了让总操作次数（也就是总成本）最小，我们应该采取贪心策略。当 pop(A) > pop(B) + mid 时，我们应该将 pop(B) 恰好增加到 pop(A) - mid。再多加就浪费了，再少加就不满足条件。这次操作的成本就是 (pop(A) - mid) - pop(B)。

但是这里有一个连锁反应！当我们增加了 pop(B) 之后，B 的新人口可能会导致它和它的其他邻居 C 之间产生新的不平衡，又需要增加 C 的人口……这样一环扣一环，要怎么处理呢？

关键的洞察点在于处理顺序！想一想，是什么决定了一个地块的人口需要增加？是它旁边有一个人口比它高得多的地块。所以，人口高的地块是“约束的来源”。我们应该优先处理这些人口高的地块，由它们来决定其周围地块需要提升到什么水平。

这启发我们应该从人口最高的陆地开始，按人口从高到低的顺序处理。

3. 用“桶”来代替优先队列

按从高到低的顺序处理，听起来很像需要一个最大优先队列（Max-Heap）。但这里的权值（人口）范围是 [0, 1000]，是一个很小且固定的整数范围。对于这种情况，我们有一个更简单高效的实现方式——桶排序的思想！

我们可以创建一个大小为 1001 的“桶”数组（vector<queue<pair<int, int>>> buckets），buckets[p] 这个桶（队列）里存放所有当前人口为 p 的陆地坐标。

check(mid) 的具体流程如下：

初始化：
- 创建一个临时网格 temp_grid，复制初始人口。
- 创建一个 visited 网格，标记是否处理过。
- 创建一个桶数组 buckets，将所有陆地按其初始人口放入对应的桶中。
- 总成本 total_cost 初始化为 0。
传播与计算：
- 我们从大到小遍历人口值 p，从 1000 到 0。
- 对于每个 p，我们处理 buckets[p] 里的所有地块。
- 从 buckets[p] 中取出一个地块 (x, y)：
  - 如果它已经被处理过（visited[x][y] == true），说明它的人口在之前被别的更高地块更新过，并且在那个更高的层级已经被作为“源头”处理了。这个桶里的它是“过时”的，直接跳过。
  - 标记 visited[x][y] = true。
  - 遍历它的 6 个邻居 (nx, ny)：
    - 如果邻居是湖泊或者出界，就忽略它。
    - 获取当前地块的人口 current_pop = temp_grid[x][y] 和邻居的人口 neighbor_pop = temp_grid[nx][ny]。
    - 如果 current_pop > neighbor_pop + mid，说明不平衡！
    - 贪心修正：我们需要把邻居的人口提升到 new_pop = current_pop - mid。
    - 累加成本：total_cost += new_pop - neighbor_pop。
    - 更新状态：更新邻居的人口 temp_grid[nx][ny] = new_pop，并将邻居 (nx, ny) 加入其新人口对应的桶 buckets[new_pop] 中，等待后续处理。
返回结果：
- 整个过程结束后，比较 total_cost 和 k。如果 total_cost <= k，则返回 true，否则返回 false。

这个从高到低处理的过程，就像是把人口看作势能，从高处向低处传播影响，直到整个系统达到一个相对平衡的状态。这个方法保证了每个地块的最终人口都是为了满足所有比它“高”的邻居的要求而达到的最小值，从而保证了总成本最小，喵~

代码实现

这是我根据上面的思路，精心为你准备的一份代码哦！注释很详细，希望能帮到你，呐~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

// 定义邻居的6个方向
const int dx[] = {-1, -1, 0, 0, 1, 1};
const int dy[] = {0, 1, -1, 1, -1, 0};

int n, m;
long long k;
vector<vector<int>> initial_grid;

// check函数，判断不平衡值为mid时是否可行
bool check(int mid) {
    long long total_cost = 0;
    
    // 使用临时网格，避免修改原始数据
    vector<vector<int>> temp_grid = initial_grid;
    
    // 桶，buckets[p]存放所有人口为p的坐标
    // 人口范围[0, 1000]，所以大小设为1001
    vector<queue<pair<int, int>>> buckets(1001);
    
    // visited数组，防止重复处理一个节点作为“源头”
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    // 初始化桶，将所有陆地放入对应的桶中
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (temp_grid[i][j] != -1) {
                buckets[temp_grid[i][j]].push({i, j});
            }
        }
    }

    // 从高到低遍历人口值
    for (int p = 1000; p >= 0; --p) {
        while (!buckets[p].empty()) {
            pair<int, int> pos = buckets[p].front();
            buckets[p].pop();
            int r = pos.first;
            int c = pos.second;

            // 如果当前节点的人口已经被更新过，
            // 并且在更高的桶里被处理过了，就跳过。
            // 这里的p是该节点最初（或上一次更新后）被放入桶时的值，
            // temp_grid[r][c]才是它的最新值。
            // 如果一个节点被更新，它的值只会变大，所以p < temp_grid[r][c]
            // 的情况是有可能发生的。但我们用visited数组来处理更普适。
            if (visited[r][c]) {
                continue;
            }
            visited[r][c] = true;

            // 检查6个邻居
            for (int i = 0; i < 6; ++i) {
                int nr = r + dx[i];
                int nc = c + dy[i];

                // 检查边界和湖泊
                if (nr < 0 || nr >= n || nc < 0 || nc >= m || temp_grid[nr][nc] == -1) {
                    continue;
                }
                
                // 当前节点的人口一定是其最新的值
                int current_pop = temp_grid[r][c];
                int neighbor_pop = temp_grid[nr][nc];

                if (current_pop > neighbor_pop + mid) {
                    int required_pop = current_pop - mid;
                    long long cost = required_pop - neighbor_pop;
                    
                    total_cost += cost;
                    // 如果成本已经超了，可以提前退出，但为了逻辑清晰，我们算完
                    // if (total_cost > k) return false;

                    temp_grid[nr][nc] = required_pop;
                    buckets[required_pop].push({nr, nc});
                }
            }
        }
    }

    return total_cost <= k;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    initial_grid.assign(n, vector<int>(m));
    int max_pop = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> initial_grid[i][j];
            if (initial_grid[i][j] > max_pop) {
                max_pop = initial_grid[i][j];
            }
        }
    }

    int low = 0, high = max_pop; // 答案的范围在[0, 初始最大人口]
    int ans = high;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1; // 尝试更小的不平衡值
        } else {
            low = mid + 1; // 当前mid太小，做不到，需要放宽
        }
    }

    cout << ans << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \cdot M \cdot \log(\text{MAX\_POP}))$
- 二分答案的部分会进行 $O(\log(\text{MAX\_POP}))$ 次迭代，其中 MAX_POP 是初始的最大人口数（最大为1000）。
- check(mid) 函数是复杂度的核心。在 check 函数中，每个陆地格子最多只会被作为“源头”（即从桶中取出并标记为 visited）一次。当一个格子被作为源头处理时，我们会遍历它的 6 个邻居。因此，这部分的总操作数和图的边数成正比，也就是 $O(N \cdot M)$ 。虽然格子会因为人口增加被多次放入桶中，但作为源头处理只有一次。所以 check 函数的复杂度是 $O(N \cdot M)$ 。
- 两者相乘，总时间复杂度就是 $O(N \cdot M \cdot \log(\text{MAX\_POP}))$ 。
空间复杂度: $O(N \cdot M)$
- 我们需要存储初始网格 initial_grid、临时网格 temp_grid 和 visited 网格，这些都是 $O(N \cdot M)$ 。
- 桶数组 buckets 本身大小是固定的（1001），但里面存储的坐标总数在最坏情况下也和格子总数相关，是 $O(N \cdot M)$ 。
- 因此，总的空间复杂度是 $O(N \cdot M)$ 。

知识点总结

二分答案: 解决“最小化最大值”或“最大化最小值”问题的经典利器。将求解问题转化为判定问题。
贪心算法: 在 check 函数中，每次都只把人口提升到恰好满足条件的水平，这是局部最优的选择，最终导向了全局最优（最小总成本）。
图的遍历与传播: 问题可以看作是在一个网格图上，根据节点权值（人口）进行信息传播。
桶/基数排序思想: 当处理的对象权值范围不大且为整数时，使用桶（数组+队列）是代替通用优先队列（堆）的一种非常高效的方式，可以把排序或优先级处理的对数因子优化掉。

希望这篇题解能让你对这类问题有更深的理解！如果有任何问题，随时可以再来问我哦，喵~

平衡 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 二分答案的框架 ​

2. 如何实现 check(mid) ​

3. 用“桶”来代替优先队列 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​