AtCoder ABC298 F - Rook Score

2huk · 2023-04-20 11:20:02 · 题解

题目描述

有一个 10^9 \times 10^9 的网格。(r_i, c_i) 的位置上写着 x_i，其余位置为 0。

找到一个点 (x, y)，使得 x 行的数字与 y 行的数字之和最大（重复计算的要只算一次）。求出最大值。

样例输入输出

数据范围

1 \le N \le 2 \times 10^5,\ 1 \le r_i,c_i,x_i \le 10^9

前置 - STL

pair<int, int> : 将两个变量关联在一起，组成一个对，这两个变量的类型都是 int。由于 pair<int, int> 过长，我们通常用加上一条语句typedef pair<int, int> PII; 用 PII 代替掉上面的 pair<int, int>。

map<PII, int> : 有序键值对容器，它的元素的键是唯一的。前面的 PII 是我们规定的键类型，后面的 int 是我们规定的值类型。

unordered_map<int, int> : 与 map 类似，无序键值对容器，它的元素的键是唯一的。前面的 int 是我们规定的键类型，后面的 int 是我们规定的值类型。

vector<PII> : 内存连续的、可变长度数组，数组中的元素类型为 int。

分析

介绍完本题需要用到的 STL 容器后，我们开始分析这道题目。

本题的值域巨大，但元素数量不多，因此我们要想一种方法把数据存储起来，

完成后，就要考虑贪心策略，寻找最优解。

以下分为两个部分叙述。

存储数据

看到这个数据范围，我们可以将数据离散化。但那样略显复杂，这里使用 STL 容器进行处理数据。

unordered_map 的内部原理是使用哈希表存储数据，因此它可以存储几乎所有数据类型（几乎的原因下面有提到）。题目中要求每一行或每一列的数字和，所以可以用 unordered_map 存储每一行和每一列的权值和。

我们还需要存储下每一个点的权值，但是如果开二维数组肯定是不可以的，因此考虑使用容器 map。

为什么不能使用 unordered_map 呢？因为我们相当于是有 3 个变量要存储，分别是横坐标，纵坐标和权值。而 unordered_map 不允许使用 pair，所以也就不能存储 3 个变量，而 map 是可以的。

以上的存储都可以在输入时完成：

unordered_map<int, int> R, C;
vector<PII> r, c; 
map<PII, int> mp;

cin >> n;

for (int i = 1; i <= n; i ++ )
{
    cin >> x >> y >> z;
    mp[{x, y}] = z;
    R[x] += z;
    C[y] += z;
}

由于要找最大值，我们会有一个意识就是需要把数据排序。但 unordered_map 是无法支持排序的，因此这里就用到了 vector。

我们可以把 unordered_map 中的所有数据再次存入 vector 中。由于 unordered_map 中的每一个值都有 Key 和 T 属性，也就是 first 和 second，所以 vector 的数据类型为 pair<int, int>，其中第一个值存储的是当前行的权值和，第二个值存储的是这一行的行数。

将元素搬到 vector 中后，就可以对其进行排序了。pair<int, int> 类型的 sort 排序是按照第一个值从小到大排序，所以排完序后还需要把数组翻转过来。

for (auto e : R) r.push_back({e.second, e.first});
for (auto e : C) c.push_back({e.second, e.first});

sort(r.begin(), r.end());
sort(c.begin(), c.end());
reverse(r.begin(), r.end());
reverse(c.begin(), c.end());

贪心寻找最优解

上面的排序都是为了这一步的贪心做准备。

如果只找最大行和最大列，并把它们相加的话，是肯定不行的。例如下面这个例子。

最大行是第 2 行，最大列是第 2 列，但是它们的和是 11，不如选 (2, 1) 点的 12 要优。所以这样的贪心策略是不行的。

由于求行和列的和的时候，需要减掉重复部分的数值，所以这个减掉的数值肯定是越小越好。

最小是多少呢？明显为 0，也就是不在这个格子上面写数字。所以我们又有了另一种贪心策略：先把行和列按数字和从大到小排序，如果令当前行为 r，当前列为 c，那么如果 (r, c) 的值为 0，就可以直接更新答案并跳出循环，否则继续更新最大值。

贪心证明：

如果当前枚举的行为 r，当前列为 c，那么由于我们已经排过序，所以以后枚举的行 r' 和列 c' 的和一定是分别小于等于当前列的。也就是 s_{r'} \le s_r,\ s_{c'} \le s_c。又由于 (r, c) 的值为 0，所以本行和本列的总和为 s_r + s_c。而 (r', c') 的值不一定为 0，若记这个数为 x，那么一定有 x \ge 0，所以 r' 行和 c' 列的总和为 s_{r'} + s_{c'} - x。很显然的是，s_r + s_c \ge s_{r'} + s_{c'} - x，所以可以停止枚举直接输出答案。

for (auto _r : r)
    for (auto _c : c)
        if (mp.find({_r.second, _c.second}) == mp.end())
        {
            ans = max(ans, _r.first + _c.first);
            break;
        }
        else ans = max(ans, _r.first + _c.first - mp[{_r.second, _c.second}]);

完整代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> PII;

int n, x, y, z, ans;

unordered_map<int, int> R, C;
vector<PII> r, c; 
map<PII, int> mp;

signed main()
{
    // 读入 
    cin >> n;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> x >> y >> z; 
        mp[{x, y}] = z;     // map 存储 (x, y) 上的值 
        R[x] += z;          // R 存储当前行上的数字和 
        C[y] += z;          // C 存储当前列上的数字和 
    }

    // 将 unordered_map 中的元素搬到 vector 中，便于排序 
    for (auto e : R) r.push_back({e.second, e.first});
    for (auto e : C) c.push_back({e.second, e.first});

    // 从大到小排序 
    sort(r.begin(), r.end());
    sort(c.begin(), c.end());
    reverse(r.begin(), r.end());
    reverse(c.begin(), c.end());

    // 贪心 
    for (auto _r : r)       // 枚举行 
        for (auto _c : c)   // 枚举列 
            if (mp.find({_r.second, _c.second}) == mp.end())        // 如果 (_r, _c) 的值为 0，更新答案后直接跳出循环 
            {
                ans = max(ans, _r.first + _c.first);
                break;
            }
            else ans = max(ans, _r.first + _c.first - mp[{_r.second, _c.second}]);      // 否则更新答案 

    cout << ans;        // 输出答案 

    return 0;
}