CF1914D Three Activities

Zinc-Acetate / 2024-01-23 / 原文

题目链接

codeforces

洛谷

题面

Winter holidays are coming up. They are going to last for $n$ days.

During the holidays, Monocarp wants to try all of these activities exactly once with his friends:

go skiing;
watch a movie in a cinema;
play board games.

Monocarp knows that, on the $i$-th day, exactly $a_i$ friends will join him for skiing, $b_i$ friends will join him for a movie and $c_i$ friends will join him for board games.

Monocarp also knows that he can't try more than one activity in a single day.

Thus, he asks you to help him choose three distinct days $x, y, z$ in such a way that the total number of friends to join him for the activities ($a_x + b_y + c_z$) is maximized.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($3 \le n \le 10^5$) — the duration of the winter holidays in days.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$) — the number of friends that will join Monocarp for skiing on the $i$-th day.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^8$) — the number of friends that will join Monocarp for a movie on the $i$-th day.

The fourth line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^8$) — the number of friends that will join Monocarp for board games on the $i$-th day.

The sum of $n$ over all testcases doesn't exceed $10^5$.

Output

For each testcase, print a single integer — the maximum total number of friends that can join Monocarp for the activities on three distinct days.

题目大意

给定三个数组 $a, b, c$ 找三个互不相同的整数 $i, j, k$ 使得 $a_i + b_j + c_k$ 的值最大.

思路

首先想到的当然是枚举 $i, j, k$ 然后找到最大值，但这种方法的时间复杂度是 $O(n^3)$ ,显然会喜提 $TLE$ .

由瞪眼法可知，因为我们只需要找到 $a_i + b_j + c_k$ 的最大值，所以我们会考虑尽可能取三个数组中更大的数。因为不能取到下标重合的数，考虑到即使 $a, b$ 取完后， $c$ 也最多选到第三大的数，所以我们只需要找到 $a, b, c$ 中各自的前三大的数，然后遍历一下找到最大值即可。排序找各自最大的三个数，时间复杂度 $O(n\log{n})$ ，~~当然可以O(n),但我懒~~.

代码

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define int long long
#define endl '\n'
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n), b(n), c(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].first;  // first记录数值
        a[i].second = i;    // second记录下标
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i].first;
        b[i].second = i;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> c[i].first;
        c[i].second = i;
    }
    sort(all(a));
    sort(all(b));
    sort(all(c));   //排序，用于取各自最大的三个数
    int ans = 0;
    for (int i = n - 3; i < n; i++)
    {
        for (int j = n - 3; j < n; j++)
        {
            if (a[i].second == b[j].second)
                continue;   // 下标相同的不符合题意
            for (int k = n - 3; k < n; k++)
            {
                if (a[i].second == c[k].second || b[j].second == c[k].second)
                    continue;
                ans = max(ans, a[i].first + b[j].first + c[k].first);
            }
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}