影响力--题解

题干中给的是切比雪夫距离的公式如果使用暴力算法需要遍历每个格子A对每个格子A都要遍历所有格子B计算代价。发现复杂度太高O((nm)2)n的二次方乘m的二次方所以这个方法不可行。这时我们要用到曼哈顿距离的转化就将距离转化为了代码实现如下#include bits/stdc.h using namespace std; int main() { // 输入输出优化加快速度 ios::sync_with_stdio(false); cin.tie(nullptr); // 1. 读取网格的行数n和列数m int n, m; cin n m; // 2. 计算总格子数并创建存储实力的数组 int total n * m; vectorints(total); // s[id] 存储每个格子的实力值 // 3. 逐行读取每个格子的实力值 // 将二维坐标(i,j)映射到一维索引 id i*m j for (int i 0; i n; i) { for (int j 0; j m; j) { cin s[i * m j]; } } // 4. 准备 u 和 v 坐标用于切比雪夫距离转换 // u i j, v i - j // 切比雪夫距离 max(|i1-i2|,|j1-j2|) (|u1-u2| |v1-v2|)/2 vectorintu(total), v(total); for (int i 0; i n; i) { for (int j 0; j m; j) { int id i * m j; // 计算一维索引 u[id] i j; // u坐标 v[id] i - j; // v坐标 } } // 5. 创建数组存储每个格子到所有格子的 |u| 之和 和 |v| 之和 vectorlonglongsum_u(total), sum_v(total); // 6. 处理 u 坐标计算每个格子的 sum_u[id] { // 6.1 创建索引数组并排序按 u 值从小到大 vectorintidx(total); iota(idx.begin(), idx.end(), 0); // idx [0,1,2,...,total-1] sort(idx.begin(), idx.end(), [](int a, int b) { return u[a] u[b]; }); // 现在 idx 按 u 值排序idx[i] 是第 i 小的 u 值对应的原始格子 id // 6.2 计算排序后的 u 值的前缀和 vectorlonglongprefix(total 1); for (int i 0; i total; i) { prefix[i 1] prefix[i] u[idx[i]]; // 前缀和前 i1 个 u 值之和 } // 6.3 对每个位置计算 |u[id] - u[others]| 之和 for (int i 0; i total; i) { int id idx[i]; // 当前格子的原始 id long long left_sum prefix[i]; // 左边所有 u 值之和 long long right_sum prefix[total] - prefix[i 1]; // 右边所有 u 值之和 int left_count i; // 左边格子数量 int right_count total - i - 1; // 右边格子数量 // 公式Σ|u_A - u_B| // (左边个数) × u_A - 左边和 右边和 - (右边个数) × u_A sum_u[id] (long long)left_count * u[id] - left_sum right_sum - (long long)right_count * u[id]; } } // 7. 处理 v 坐标计算每个格子的 sum_v[id] // 逻辑完全同上只是把 u 换成 v { // 7.1 创建索引数组并按 v 值排序 vectorintidx(total); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [](int a, int b) { return v[a] v[b]; }); // 7.2 计算排序后的 v 值的前缀和 vectorlonglongprefix(total 1); for (int i 0; i total; i) { prefix[i 1] prefix[i] v[idx[i]]; } // 7.3 对每个位置计算 |v[id] - v[others]| 之和 for (int i 0; i total; i) { int id idx[i]; long long left_sum prefix[i]; long long right_sum prefix[total] - prefix[i 1]; int left_count i; int right_count total - i - 1; sum_v[id] (long long)left_count * v[id] - left_sum right_sum - (long long)right_count * v[id]; } } // 8. 输出结果 for (int i 0; i n; i) { for (int j 0; j m; j) { int id i * m j; // 当前格子的 id // 切比雪夫距离总和 (|u|之和 |v|之和)/2 long long total_dist (sum_u[id] sum_v[id]) / 2; // 总代价 距离总和 × 实力 long long cost total_dist * s[id]; // 输出每行最后一个数字后换行 cout cost (j m - 1 ? \n : ); } } return 0; }