喵~ 主人，你好呀！今天由我，你最可爱的小猫娘，来为你讲解一道关于假期安排的有趣问题，嘻嘻。Monocarp 想要和他的一大堆朋友们玩得开心，我们当然要帮他找出最棒的计划啦！

D. Three Activities

---

题目大意

简单来说，Monocarp 有一个为期 n 天的寒假，他想在这 n 天里完成三项活动：滑雪、看电影和玩桌游，每项活动都只做一次。

最重要的是，这三项活动必须在 三个不同的日子 进行。

我们拿到了三份日程表，喵~

• a 数组：a[i] 表示第 i 天约好一起滑雪的朋友数量。
• b 数组：b[i] 表示第 i 天约好一起看电影的朋友数量。
• c 数组：c[i] 表示第 i 天约好一起玩桌游的朋友数量。

我们的任务是帮助 Monocarp 挑选三个 不同 的日子 x, y, z，分别用来滑雪、看电影和玩桌游，使得总的参与朋友数 a[x] + b[y] + c[z] 最大化！

---

解题思路

一看到要让总和最大，我们的小脑袋里第一个蹦出来的想法肯定是贪心，对不对呀？嘻嘻~

最贪心的想法就是：

1. 滑雪选朋友最多的那天。
2. 看电影也选朋友最多的那天。
3. 玩桌游同样选朋友最多的那天。

然后把这三天的朋友数加起来，不就是最大了吗？

等一下，喵！ 题目里有个很重要的限制哦：三天必须是不同的！如果滑雪最多朋友的一天，恰好也是看电影最多朋友的一天，那这个计划就不行啦，因为一天只能做一件事。

那怎么办呢？难道要放弃贪心的想法吗？

别急嘛，主人。我们可以稍微变通一下。我们的目标是让 a[x] + b[y] + c[z] 最大。这说明 a[x], b[y], c[z] 这三个值本身肯定都要很大才行。所以，最优解里的 x、y、z 这三天，很大概率就是各自活动里朋友数排名前几的天。

我们可以做一个大胆但正确的猜想：最终的最优解，一定是由各项活动朋友数排名前 3 的日期组合而成的。

为什么是前 3 呢？让本猫娘来给你证明一下，喵~

假设我们的最优解是 a[x] + b[y] + c[z]，并且我们选的滑雪日 x 并不是滑雪朋友数排名前三的日子。 我们来看看滑雪朋友数最多的三天，分别是 d_a1, d_a2, d_a3。 我们选择的看电影日 y 和桌游日 z 最多只能占用掉 d_a1, d_a2, d_a3 中的两个。也就是说，这三天里至少还剩下一天，我们叫它 d_a_free，它既不等于 y 也不等于 z。 因为 x 不是前三名，而 d_a_free 是前三名之一，所以 a[d_a_free] 肯定大于等于 a[x]。 那么，我们把滑雪日从 x 换成 d_a_free，得到的新的总朋友数 a[d_a_free] + b[y] + c[z] 只会比原来的更大或者相等，而且三个日期 d_a_free, y, z 仍然是不同的。 这就说明，最优解的滑雪日一定可以在前三名里找到！同理，看电影和玩桌游的日子也一定可以在它们各自的前三名里找到。

这样一来，问题就变得非常简单啦！

我们的算法步骤就是：

1. 把每天滑雪、看电影、玩桌游的朋友数和对应的日期（也就是下标）存起来。用一个 pair 或者 struct 就很方便，比如 (朋友数, 日期)。
2. 分别对这三个活动的列表，按照朋友数从高到低排序。
3. 现在我们拿到了每个活动的前三名。我们只需要在这 3 (滑雪) × 3 (电影) × 3 (桌游) = 27 种组合里进行暴力搜索。
4. 对于每一种组合，检查选出的三个日期是不是互不相同。
5. 如果日期不同，就计算总的朋友数，然后更新我们的最大值答案。
6. 遍历完所有 27 种组合后，找到的那个最大值就是最终答案啦！是不是很简单，喵~

---

题解代码

这是本猫娘为你准备好的 C++ 代码，加了详细的注释哦！

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

// 设置快速输入输出，让程序跑得像小猫一样快，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 解决单个测试用例的函数
void solve() {
    int n;
    std::cin >> n;

    // 使用 pair 来存储 (朋友数量, 日期下标)
    std::vector<std::pair<int, int>> a(n), b(n), c(n);

    // 读取滑雪数据
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i].first;
        a[i].second = i; // 记录原始的日期下标
    }
    // 读取电影数据
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i].first;
        b[i].second = i;
    }
    // 读取桌游数据
    for (int i = 0; i < n; ++i) {
        std::cin >> c[i].first;
        c[i].second = i;
    }

    // 分别对三个活动按朋友数降序排序
    // rbegin() 和 rend() 是反向迭代器，可以方便地实现降序排序
    std::sort(a.rbegin(), a.rend());
    std::sort(b.rbegin(), b.rend());
    std::sort(c.rbegin(), c.rend());

    long long max_friends = 0;

    // 只需要检查每个活动的前3名日期的所有组合
    // 因为 n >= 3，所以我们总能安全地访问下标 0, 1, 2
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                // 检查选出的三个日期下标是否都不同
                if (a[i].second != b[j].second && a[i].second != c[k].second && b[j].second != c[k].second) {
                    // 计算当前组合的总朋友数
                    long long current_sum = (long long)a[i].first + b[j].first + c[k].first;
                    // 更新最大值
                    if (current_sum > max_friends) {
                        max_friends = current_sum;
                    }
                }
            }
        }
    }

    std::cout << max_friends << "\n";
}

int main() {
    fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

这道题虽然不难，但里面包含了一些在算法竞赛中非常有用的思想和技巧哦！

1. 贪心思想的局限与优化

   • 贪心算法 (Greedy Algorithm)：总是做出在当前看来是最好的选择。但这道题里，单纯的局部最优（选各自的第一名）不一定能得到全局最优解，因为有“日期不能重复”的约束。
   • 优化思路：我们没有完全抛弃贪心，而是通过分析，意识到最优解的构成元素（日期）一定来自于一个很小的“候选池”（各自的前三名）。

2. 减小搜索空间 (Reducing the Search Space)

   • 这道题最核心的技巧！直接暴力搜索所有日期的组合 n * (n-1) * (n-2) 肯定会超时。
   • 通过逻辑推导（就是本猫娘上面讲的证明~），我们把无限的可能性缩小到了有限的 3 * 3 * 3 = 27 种组合。
   • 在庞大的数据面前，先思考如何缩小需要检查的范围，是解决很多问题的关键一步。

3. std::pair 和排序

   • 在排序时，我们不仅关心值的大小，还关心这个值原来的位置。std::pair<int, int> 或者自定义结构体是解决这个问题的经典方法，可以将数值和它的原始索引绑定在一起。
   • std::sort 是 C++ STL 中非常强大的排序工具，熟练使用它可以大大提高编码效率。

好啦，今天的讲解就到这里啦！希望主人能够明白。如果还有什么问题，随时可以再来找我哦，喵~ ❤️