语言月赛 202409 距离

思路描述

• 维护一个二维数组 d[105][105]，用来存储每个同学 $p$ 对同学 $q$ 的当前好感度，初始全部为 $0$。
• 维护一个变量 mx，记录当前所有好感度中的最大值，初始为 $0$。
• 对于每一件事情：
• 根据操作类型 op：
  • 若 op == 1，执行加法：d[a][b] += c。
  • 若 op == 2，执行减法：d[a][b] -= c。
• 更新后，检查 d[a][b] 是否大于 mx，若是则更新 mx。
• 注意，减法可能会导致之前的最大值被减小，因此需要重新计算最大值：
  • 一种简单但效率较低的方式是每次操作后遍历整个 d 数组，找出当前最大值。
  • 由于 $n \leq 100$，最多 $100 \times 100 = 10,000$ 个元素，且 $m \leq 100$，这种做法是可行的。
• 输出每次操作后的 mx。

---

实现示例

#include <bits/stdc++.h>
using namespace std;
int d[105][105];
int main() 
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int op, a, b, c;
        cin >> op >> a >> b >> c;
        if (op == 1) d[a][b] += c;
        else d[a][b] -= c;
        int mx = 0;
        // 重新遍历所有位置求最大值
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                mx = max(mx, d[i][j]);
        cout << mx << "\n";
    }
    return 0;
}

算法复杂度

• 每次操作更新一个元素并遍历数组找最大值：$O(n^2)$。
• 总共 $m$ 次操作，整体复杂度为 $O(m \times n^2)$，对于 $n,m \leq 100$，可接受。

---