从今天开始,随机开始每日一题~
题目内容
原题链接
给定一个 1 0 9 × 1 0 9 10^9\times 10^9 109×109 大小的矩阵,给出其中 n n n 个点的权值,第 i i i 个点 ( x i , y i ) (x_i,y_i) (xi,yi) 的权值为 w i w_i wi ,剩下的 1 0 18 − n 10^{18}-n 1018−n 个点的权值为 0 0 0 。
现在让你选择一个 x x x 和一个 y y y ,使得计算所有的点中 x i = x x_i=x xi=x 或 y i = y y_i=y yi=y 的点的权值之和最大。
数据范围
1
≤
n
≤
2
×
1
0
5
1\leq n\leq 2\times 10^5
1≤n≤2×105
1
≤
x
i
,
y
i
,
w
i
≤
1
0
9
1\leq x_i,y_i,w_i\leq 10^9
1≤xi,yi,wi≤109
(
x
i
,
y
i
)
≠
(
x
j
,
y
j
)
,
i
≠
j
(x_i,y_i)\neq (x_j,y_j), i\neq j
(xi,yi)=(xj,yj),i=j
题解
思路:思维
首先对于每个 x x x 和 y y y ,计算所有点中 x i = x x_i=x xi=x 的权值和 r o w [ x ] row[x] row[x] ,以及所有点中 y i = y y_i=y yi=y 的权值和 c o l [ y ] col[y] col[y] 。
如果 ( x , y ) (x, y) (x,y) 是输入的有权值的 n n n 个点中的一个,答案为 r o w [ x ] + c o l [ y ] − w x , y row[x]+col[y]-w_{x,y} row[x]+col[y]−wx,y ,此时枚举每个点即可。
否则答案为 r o w [ x ] + c o l [ y ] row[x]+col[y] row[x]+col[y] ,这样暴力枚举时间复杂度为: O ( n 2 ) O(n^2) O(n2)
考虑如何优化?
我们可以枚举 x x x ,然后考虑所有的 y y y ,满足 ( x , y ) (x, y) (x,y) 并不是输入的 n n n 个点中的任意一个。
我们要求答案最大,所以考虑对 x x x 按照 r o w [ x ] row[x] row[x] 从大到小排序,对 y y y 按照 c o l [ y ] col[y] col[y] 从大到小排序。如果遇到 ( x , y ) (x,y) (x,y) 在输入的 n n n 个点中出现过,则跳过。因为至多 n n n 个点,同时我们要求的是最大值,所以一旦遇到一个点 ( x , y ) (x, y) (x,y) 不在 n n n 个点中,则更新答案,并退出当前 x x x 所在的循环。文章来源:https://www.toymoban.com/news/detail-670169.html
时间复杂度: O ( n log n ) O(n\log n) O(nlogn)文章来源地址https://www.toymoban.com/news/detail-670169.html
代码
#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;
}
到了这里,关于【每日一题】ABC256F-Rook Score | 思维 | 中等的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!