从今天开始，随机开始每日一题~

题目内容

原题链接

给定一个 $10^9\times 10^9$ 大小的矩阵，给出其中 $n$ 个点的权值，第 $i$ 个点 $(x_i,y_i)$ 的权值为 $w_i$ ，剩下的 $10^{18}-n$ 个点的权值为 $0$ 。

现在让你选择一个 $x$ 和一个 $y$ ，使得计算所有的点中 $x_i=x$ 或 $y_i=y$ 的点的权值之和最大。

数据范围

$1\le n\le 2\times 10^5$
$1\le x_i,y_i,w_i\le 10^9$
$(x_i,y_i)\ne (x_j,y_j),i\ne j$

题解

思路：思维

首先对于每个 $x$ 和 $y$ ，计算所有点中 $x_i=x$ 的权值和 $row[x]$ ，以及所有点中 $y_i=y$ 的权值和 $col[y]$ 。

如果 $(x,y)$ 是输入的有权值的 $n$ 个点中的一个，答案为 $row[x]+col[y]-w_{x,y}$ ，此时枚举每个点即可。

否则答案为 $row[x]+col[y]$ ，这样暴力枚举时间复杂度为：$O(n^2)$

考虑如何优化？

我们可以枚举 $x$ ，然后考虑所有的 $y$ ，满足 $(x,y)$ 并不是输入的 $n$ 个点中的任意一个。

我们要求答案最大，所以考虑对 $x$ 按照 $row[x]$ 从大到小排序，对 $y$ 按照 $col[y]$ 从大到小排序。如果遇到 $(x,y)$ 在输入的 $n$ 个点中出现过，则跳过。因为至多 $n$ 个点，同时我们要求的是最大值，所以一旦遇到一个点 $(x,y)$ 不在 $n$ 个点中，则更新答案，并退出当前 $x$ 所在的循环。

时间复杂度：$O(n\log n)$

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<pair<int, int>, int> mp;
    map<int, ll> row, col;
    // 统计点中每个 r 的总和，点中每个 c 的总和
    for (int i = 0; i < n; ++i) {
        int r, c, w;
        cin >> r >> c >> w;
        row[r] += w;
        col[c] += w;
        mp[make_pair(r, c)] = w;
    }

    ll ans = 0;
    // 首先考虑所有的点
    for (auto it: mp) {
        int r = it.first.first;
        int c = it.first.second;
        int w = it.second;
        ll rv = row[r], cv = col[c];
        ans = max(ans, rv + cv - w);
        ans = max({ans, rv, cv});
    }

    // 对于每个 (x, y) 来说，找到不和 x 构成 y 的最大 y
    // 构造每个 x 和每个 y
    vector<pair<ll, int>> X(row.size()), Y(col.size());
    int i = 0;
    for (auto it: row) {
        X[i] = make_pair(it.second, it.first);
        i += 1;
    }

    i = 0;
    for (auto it: col) {
        Y[i] = make_pair(it.second, it.first);
        i += 1;
    }

    sort(X.begin(), X.end(), greater<>());
    sort(Y.begin(), Y.end(), greater<>());

    for (auto& [valx, u]: X) {
        // 因为一共有 2e5 个点 ，枚举的每个 x ，也就是最多会将 2e5 个点
        for (auto& [valy, v]: Y) {
            if (mp.count(make_pair(u, v))) continue;
            ans = max(ans, valx + valy);
            break;
        }
    }

    cout << ans << "\n";

    return 0;
}