牛客小白月赛59 F.困难卷积(暴力)牛客小白月赛59 F.困难卷积(暴力)

218 阅读 0 评论 144 点赞

我是靠谱客的博主怡然小甜瓜，这篇文章主要介绍牛客小白月赛59 F.困难卷积(暴力)牛客小白月赛59 F.困难卷积(暴力)，现在分享给大家，希望可以做个参考。

牛客小白月赛59 F.困难卷积(暴力)

题目有个很重要的条件 $a_i,sum b_ile 10^7$

那么显然最多不同的 $a_i$ 个数为： $10^7$ 。

则 $m \leq 4000$ 。那么我们用map存值，然后二重循环暴力算即可。

时间复杂度： $O(m^2)$

#include<bits/stdc++.h>
using namespace std;
int main(){
    map<int,int>m1,m2;
    int n,i,x;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>x;
        m1[x]++;
    }
    for(i=0;i<n;i++){
        cin>>x;
        m2[x]++;
    }
    long long res=0;
    for(auto i:m1){
        for(auto j:m2){
            res+=1ll*i.second*j.second*((int)sqrt(abs(i.first-j.first)));
        }
    }
    cout<<res;
    
}