【每日一题】ABC256F-Rook Score | 思维 | 中等

这篇具有很好参考价值的文章主要介绍了【每日一题】ABC256F-Rook Score | 思维 | 中等。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

题目内容

原题链接

给定一个 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 1018n 个点的权值为 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 1n2×105
1 ≤ x i , y i , w i ≤ 1 0 9 1\leq x_i,y_i,w_i\leq 10^9 1xi,yi,wi109
( 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 所在的循环。

时间复杂度: 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【每日一题】ARC158B - Sum-Product Ratio | 数学 | 中等

    原题链接 给定一个长度为 n n n 的数组,选择三个下标不同元素 x , y , z x,y,z x , y , z ,问 x + y + z x y z frac{x+y+z}{xyz} x yz x + y + z ​ 的最大值和最小值是多少。 1 ≤ n ≤ 2 ⋅ 1 0 5 1leq nleq 2cdot 10^5 1 ≤ n ≤ 2 ⋅ 1 0 5 − 1 0 6 ≤ x i ≤ 1 0 6 , x i ≠ 0 -10^6leq x_ileq 10^6,x_ineq 0 − 1 0

    2024年02月07日
    浏览(42)
  • 【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资

    目录 今日知识点: 两两点匹配问题,注意去重方式的dfs的写法(组内升序即可) 二维图形的状态压缩,存下所有的合法状态然后暴力遍历 dfs的优化剪枝 二项式定理 最大边权和  俄罗斯方块 ABC Puzzle lnc的工资                    318D 题意:给你n个点的带权w的完全无向图

    2024年01月21日
    浏览(71)
  • 算法|每日一题|H 指数|二分

    原题地址: 力扣每日一题:H 指数 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每

    2024年02月08日
    浏览(42)
  • 每日一题之常见的排序算法

    排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放,比较的是相邻的两个元素。 时间复杂度:

    2024年02月13日
    浏览(42)
  • 算法每日一题:赎金信 | 字符和整数

    hello,大家好,我是星恒 今天给大家带来的题目是一道简单题目,主要帮大家复习一下字符串和字符的相关操作 给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransom

    2024年01月21日
    浏览(44)
  • 《算法竞赛·快冲300题》每日一题:“彩虹数”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 彩虹数 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1840 【题目描述】 彩虹数:一个无

    2024年02月09日
    浏览(49)
  • 《算法竞赛·快冲300题》每日一题:“超级骑士”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 超级骑士 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1810 【题目描述】 现在在一个无

    2024年02月17日
    浏览(52)
  • 《算法竞赛·快冲300题》每日一题:“糖果配对”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 糖果配对 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1735 【题目描述】 现在有N个小朋

    2024年02月12日
    浏览(46)
  • 《算法竞赛·快冲300题》每日一题:“点灯游戏”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 点灯游戏 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1134 【题目描述】 有一个n*n的灯

    2024年02月08日
    浏览(48)
  • 罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1812 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定一个长度为 n 的排列 a,需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出 最小需要移动的元素个数 。 【输入格式】 第一行为正整数 n,1≤n≤100000。

    2024年02月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包