XTU 1250
6667 단어 php
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어 쩔 수 없 이 자신 이 멍청 하 다 고 말 할 수 밖 에 없 었 다.이렇게 간단 하 다 니,그 때 는 그 럴 리 가 없 었 다.
n 개 a,m 개 b 의 상승 누적 과
사고방식:중 복 된 a 와 b 를 찾아내 면 매우 복잡 도 를 줄 일 수 있다
1 #include
2 #include
3 #include <string.h>
4 #include
5
6 int a[100005],b[100005],suma[1000005],sumb[1000005];
7 long long ans;
8
9 int main()
10 {
11 int m,n,acut,bcut,tmp;
12 while(~scanf("%d%d",&m,&n))
13 {
14 acut = 0,bcut = 0;
15 memset(suma,0,sizeof(suma));
16 memset(sumb,0,sizeof(sumb));
17 for(int i = 1;i<=m;i++)
18 {
19 scanf("%d",&tmp);
20 if(suma[tmp]==0)
21 a[acut++] = tmp;
22 suma[tmp]++;
23 }
24 for(int i = 1;i<=n;i++)
25 {
26 scanf("%d",&tmp);
27 if(sumb[tmp]==0)
28 b[bcut++] = tmp;
29 sumb[tmp]++;
30 }
31 ans = 0;
32 for(int i = 0;i)
33 for(int j = 0;j)
34 {
35 ans+=(long long ) suma[a[i]]*sumb[b[j]]*(long long )(sqrt(abs(a[i]-b[j])));
36 }
37 printf("%lld
",ans);
38 }
39 return 0;
40 } 다음으로 전송:https://www.cnblogs.com/Tree-dream/p/6540096.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Laravel - 변환된 유효성 검사 규칙으로 API 요청 제공동적 콘텐츠를 위해 API를 통해 Laravel CMS에 연결하는 모바일 앱(또는 웹사이트) 구축을 고려하십시오. 이제 앱은 CMS에서 번역된 콘텐츠를 받을 것으로 예상되는 다국어 앱이 될 수 있습니다. 일반적으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
