[数据结构与算法]CF Global Round 19 E Best Pair

题目描述??

????

解题思路

1. 首先明确 ：对于一个 $n$ 长度的数组 $arr[]$ ，最多只能有 $\sqrt{n}$ 个不同的 $cn{t}_x$ , 可以通过 求和公式推导
2. 这样我们就可以通过枚举 $cn{t}_x$ ，$cn{t}_y$ 来贪心求解 —— 目标求解 : max ? { ( c n t x + c n t y ) ? ( x + y ) } \max\{(cnt_x + cnt_y) * (x + y)\} max{(cntx?+cnty?)?(x+y)} ，则当 $cn{t}_x$，$cn{t}_y$ 确定时 ， 只要满足 max ? { x + y } \max\{x + y\} max{x+y}即可 , 可以用 优先队列 + $BFS$ 来求解

代码参考

// 题目链接 :
// [E](https://codeforces.com/contest/1637/problem/E)
#include <bits/stdc++.h>
using namespace::std;
#define x first
#define y second
const int MOD = 1e9 + 7;
using LL = long long;
using PII = pair<int,int>;
const int N = 3e5 + 7;
const int M = 1e9 + 7;
int n,m,a,b,c;
int w[N];
void solve() {
    cin >> n >> m;
    unordered_map<int,vector<int>> mp;// 存每一个 cnt 的分组
    set<PII> bad;
    for(int i = 0;i < n;i ++) {
        cin >> w[i];
    }
    sort(w,w + n);
    for(int i = 0;i < n;) {
        int len = 1;
        while(i + 1 < n && w[i + 1] == w[i]) len ++ , i ++;
        mp[len].push_back(w[i]);
        i ++;
    }
    // 确定 bad pairs
    for(int i = 0;i < m;i ++) {
        cin >> a >> b;
        bad.insert({a,b});
    }
    LL res = 0;
    // 枚举每一个 cnt
    for(auto& [k1,v1] : mp) {
        for(auto& [k2,v2] : mp) {
            if(k1 > k2) continue;
            auto cmp = [&](PII& a,PII& b) {
                return v1[a.x] + v2[a.y] < v1[b.x] + v2[b.y];
            };
            priority_queue<PII,vector<PII>,decltype(cmp)> q(cmp);
            unordered_set<LL> st;// 标记队列中的信息
            q.push({v1.size() - 1 , v2.size() - 1});
            while(!q.empty()) {
                auto t = q.top(); q.pop();
                a = v1[t.x];
                b = v2[t.y];
                if((LL) (k1 + k2) * (a + b) <= res) break;
                if(a != b) {
                    if(a > b) swap(a,b);
                    if(!bad.count({a,b})) {
                        res = (LL) (k1 + k2) * (a + b);
                        break;
                    }
                }
                if(t.x && !st.count((LL) (t.x - 1) * M + t.y)) {
                    q.push({t.x - 1,t.y});
                    st.insert((LL) (t.x - 1) * M + t.y);
                }
                if(t.y && !st.count((LL) t.x * M + t.y - 1)) {
                    q.push({t.x,t.y - 1});
                    st.insert((LL) t.x * M + t.y - 1);
                }
            }
        }
    }
    cout<<res<<"\n";
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while(T --) solve();
    return 0;
}