XTU 1250 Super Fast Fourier Transform 暴力 解题报告

Bobo has two sequences of integers  {a1,a2,…,an}  and  {b1,b2,…,bm} . He would like to find

∑i=1n∑j=1m⌊|ai−bj|−−−−−−−√⌋.

Note that  ⌊x⌋  denotes the maximum integer does not exceed  x , and  |x|  denotes the absolute value of  x .

Input

The input contains at most  30  sets. For each set:

The first line contains  2  integers  n,m  ( 1≤n,m≤105 ).

The second line contains  n  integers  a1,a2,…,an .

The thrid line contains  m  integers  b1,b2,…,bm .

( ai,bi≥0,a1+a2+⋯+an,b1+b2+…,bm≤106 )

Output

For each set, an integer denotes the sum.

Sample Input

1 2
1
2 3
2 3
1 2
3 4 5
      

Sample Output

2
7      

思路：由于题目说明(ai,bi≥0,a1+a2+⋯+an,b1+b2+…,bm≤106)，可以知道，肯定会有很多重复的数据，所以暴力即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1001000;

int a, b, na[N], nb[N], ca[N], cb[N], cnta, cntb;

int main()
{
    int n, m;
    long long ans;
    while(~scanf("%d%d", &n, &m))
    {
        cnta = cntb = 0;
        memset(na, 0, sizeof(na));
        memset(nb, 0, sizeof(nb));
        ans = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &a);
            if(na[a] == 0) ca[cnta++] = a;
            na[a]++;
        }

        for(int i = 0; i < m; i++)
        {
            scanf("%d", &b);
            if(nb[b] == 0) cb[cntb++] = b;
            nb[b]++;
        }

        for(int i = 0; i < cnta; i++)
        {
            for(int j = 0; j < cntb; j++)
            {
                ans += (na[ca[i]] * nb[cb[j]] * (int)sqrt(fabs(ca[i] - cb[j])));
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}