Codeforces1637E Best Pair

tags

枚举 暴力

中文题面

给你一个长度为 $n$ 的数组 $a$ 。设 $cn{t}_x$ 是数组中等于 $x$ 的元素个数。再将 $f(x,y)$ 定义为 $(cn{t}_x+cn{t}_y)\cdot (x+y)$ 。

此外，我们还得到了 $m$ 个坏数对 $(x_i,y_i)$ 。请注意，如果 $(x,y)$ 是一对坏数组，那么 $(y,x)$ 也是坏数组。

你的任务是在所有的 $(u,v)$ 中找出 $f(u,v)$ 的最大值，使得 $u\ne v$ 这一对不是坏的，并且 $u$ 和 $v$ 都出现在数组 $a$ 中。可以保证存在这样的一对。
输入

第一行包含一个整数 $t$ ( $1\le t\le 10,000$ )–测试用例数。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ( $2\le n\le 3\cdot 10^5$ , $0\le m\le 3\cdot 10^5$ )–数组的长度和坏对的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 10^9$ )。( $1\le a_i\le 10^9$ ) - 数组元素。

接下来的 $m$ 行的 $i$ -th 包含两个整数 $x_i$ 和 $y_i$ ( $1\le x_i<y_i\le 10^9$ )，这两个整数代表一对坏数组。保证输入中不会出现两次坏对。同时也保证 $cn{t}_{x_i}>0$ 和 $cn{t}_{y_i}>0$ 。

保证每个测试用例中都有一对整数 $(u,v)$ , $u\ne v$ 不是坏数，而且这两个数字都出现在 $a$ 中。

保证 $n$ 和 $m$ 的总和不超过 $3\cdot 10^5$ 。

思路

经过半天的转化发现题目给定的式子没有什么很好的转化方法，我们还是把它保持原样，设想我们现在枚举 $cn{t}_x$ 和 $cn{t}_y$，此时要让 $f(x,y)$ 最大只需要选计数为 $cn{t}_x$ 中最大的数作为 $x$ 和计数为 $cn{t}_y$ 中最大的数作为 $y$，考虑在这个数组中有多少种不同的计数，假设有 $k$ 种，那最多种的情况是 $1+2+...+k=n$，由等差数列可知 $k\approx \surd n$，那么枚举 $cn{t}_x$ $cn{t}_y$ 只需要 $n$ 的复杂度，每次找出的最大的 $x$ $y$ 应该排除掉坏数对，而这种排除最多进行 $m$ 次。最后为了只枚举出现过的 $cn{t}_x$ 和 $cn{t}_y$ 使用 $map$，总时间复杂度 $O((nlog\surd n+m)logm)$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)3e5 + 5
#define pdd pair<double, double>
#define pii pair<int, int>

int a, b, c, d, x, y, n, m, t, k, q, l, r, p, z, h;
int num[N];
string s;
map<int, int> cnt;
map<pii, int> bad;
map<int, vector<int>> mp;
vector<int> all;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	// 注意根据数据量调整N的大小
    cin >> t;
    while (t--) {
        cnt.clear();
        mp.clear();
        all.clear();
        bad.clear();
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> x;
            cnt[x]++;
        }
        while (m--) {
            cin >> x >> y;
            bad[{x,y}] = bad[{y,x}] = 1;
        }
        for (auto it = cnt.begin(); it != cnt.end(); it++) {
            mp[it->second].push_back(it->first);
            all.push_back(it->second);
        }
        for (auto it = mp.begin(); it != mp.end(); it++) sort(it->second.begin(), it->second.end());
        sort(all.begin(), all.end());
        int len = unique(all.begin(), all.end()) - all.begin();
        int mx = -1e18;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                auto& lv = mp[all[i]];
                auto& rv = mp[all[j]];
                int f = 0;
                for (l = lv.size() - 1; l >= 0; l--) {
                    for (r = rv.size() - 1; r >= 0; r--) {
                        if (bad.count({lv[l], rv[r]}) || bad.count({rv[r], lv[l]})) continue;
                        mx = max(mx, (all[i]+all[j])*(lv[l]+rv[r]));
                        if (r == rv.size() - 1) f = 1;
                        break;
                    }
                    if (f) break;
                }
            }
            // j == i单独
            int f = 0;
            auto& v = mp[all[i]];
            for (l = v.size() - 1; l >= 0; l--) {
                for (r = l - 1; r >= 0; r--) {
                    if (bad.count({v[l], v[r]}) || bad.count({v[r], v[l]})) continue;
                    mx = max(mx, (all[i]+all[i])*(v[l]+v[r]));
                    if (r == l - 1) f = 1;
                    break;
                }
                if (f) break;
            }
        }
        cout << mx << '\n';
    }
	return 0;
}