a[i]之和小于N的含义

例题

题目

要求一个暴力算是 \(O(n^2)\) 的东西

同时题目保证 \(\sum a[i] \leq 10^7\)

题解

\(\sum a[i] \leq 10^7\) 的含义是 \(a[i]\) 的值的种类数不超过 \(sqrt(10^7)\) 的意思

这样就可以用pair存储每个值出现的次数，并在 \(O(n * sqrt(n))\) 内可以求出答案

// #pragma GCC optimize(2)

#include<bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define pii pair<int,int>

#define pb push_back

using namespace std;

const int N = 3e6 + 10;

int n, a[N], b[N];

map<int, int> ma, mb;

inline int cal(int a, int b) {

    return floor(sqrt(abs(a - b)));

}

int main(){

    cin >> n;

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), ma[a[i]]++;

    for(int i = 1; i <= n; i++) scanf("%d", &b[i]), mb[b[i]]++;

    ll ans = 0;

    for(auto i : ma) {

        for(auto j : mb) {

            ans += 1ll * i.second * j.second * cal(i.first, j.first);

        }

    }

    printf("%lld\n", ans);

    system("pause");

    return 0;

}

巴特西

a[i]之和小于N的含义

例题

题目

题解

最新文章

热门文章