首页 > 其他 > 详细

XTUOJ1250 Super Fast Fourier Transform 暴力

时间:2016-06-18 10:14:43      阅读:203      评论:0      收藏:0      [点我收藏+]

分析:因为加起来不超过1e6,所以最多有1000+个不同的数

做法:离散化搞就好了

技术分享
#include <cstdio>
#include <iostream>
#include <ctime>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int a[N],b[N],c[N],k1[N],k2[N];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
      for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        c[i]=a[i];
      }
      sort(a+1,a+1+n);
      int cnt1=unique(a+1,a+1+n)-a-1;
      memset(k1,0,sizeof(k1));
      for(int i=1;i<=n;++i){
        ++k1[lower_bound(a+1,a+1+cnt1,c[i])-a];
      }
      for(int i=1;i<=m;++i){
        scanf("%d",&b[i]);
        c[i]=b[i];
      }
      sort(b+1,b+1+m);
      int cnt2=unique(b+1,b+1+m)-b-1;
      memset(k2,0,sizeof(k2));
      for(int i=1;i<=m;++i){
        ++k2[lower_bound(b+1,b+1+cnt2,c[i])-b];
      }
      LL ret=0;
      for(int i=1;i<=cnt1;++i){
        for(int j=1;j<=cnt2;++j){
          LL tmp=sqrt(abs(a[i]-b[j]));
          ret+=1ll*k1[i]*k2[j]*tmp;
        }
      }
      printf("%I64d\n",ret);
    }
    return 0;
}
View Code

 

XTUOJ1250 Super Fast Fourier Transform 暴力

原文:http://www.cnblogs.com/shuguangzw/p/5595720.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!