CF1914D Three Activities

题目大意

给定三个数组 \(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})\) .

代码

#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;
}