https://ac.nowcoder.com/acm/contest/43844/F
- 暴力去求的复杂度为n^n
- 如果序列a的个数为lengtha，序列b的个数为lengthb，序列a的数字全为numa，序列a的数字全为numb,那么lengtha即为numa出现的次数，lengthb即为numb出现的次数，则答案为
- 观察数字出现的个数，考虑极端的情况，每个数字都只出现一次，出现的次数要尽可能多，那么就是一个从0开始，公差为1的等差数列。
- 说明一个序列中数字的种类最多为sqrt（2e7）.
- 扫一遍两个序列，把每个序列中数字出现的次数存储下来，最后暴力求出答案，复杂的为O(2e7),可以承受
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int ar[3000010];
int br[3000010];
vector<pair<int,int>> ap,bp;
int main(){
int n;
int num;
cin>>n;
memset(ar,0,sizeof(ar));
memset(br,0,sizeof(br));
for(int i = 1;i<=n;i++) {
cin>>num;
ar[num]++;
}
for(int i = 1;i<=n;i++) {
cin>>num;
br[num]++;
}
// cout<<1<<endl;
for(int i = 0;i<=3000000;i++){
if(ar[i]) ap.push_back({i,ar[i]});
}
for(int i = 0;i<=3000000;i++){
if(br[i]) bp.push_back({i,br[i]});
}
// cout<<ap.size()<<endl;
long long ans = 0;
for(auto pa:ap){
for(auto pb:bp){
ans += (long long)pa.second*(long long)pb.second*floor(sqrt(abs(pa.first-pb.first)));
}
}
cout<<ans<<endl;
}