社区讨论

求助

lliufukang
学术版参与者 2已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@loc5m7y7
此快照首次捕获于
2023/10/30 08:20
2 年前
此快照最后确认于
2023/11/04 14:38
2 年前
查看原帖

题目描述

给出一个长度为 nn 的数组 a[]a[]，请计算所有的(ai−aj)2(a_i-a_j)^2的和，其中 i>ji>j。写成公式为：\sum_{i=2}^n$$\sum_{j=1}^{i-1}$$(a_i-a_j)^2（1≤j<i≤n1 \le j < i \le n)。

输入

输入的第一行有一个数 nn（2≤n≤3×1052 \le n \le 3 \times 10^5），表示有 nn 个数。
第二行有 nn 个数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n（∣ai∣≤200|a_i| \le 200）两数之间用空格分开。

输出

一行一个数，表示答案。

Input1

INPUT1
3
2 8 4

Output1

OUTPUT1
56

Input2

INPUT2
5
-5 8 9 -4 -3

Output2

OUTPUT2
950

CODE

CPP
#include<bits/stdc++.h>
using namespace std;
const int maxN=3e5+9;
int n,d[409];
long long ans;
int read(){
    int s=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (isdigit(ch)){
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s*f;
}
int main(){
    n=read();
    for (int i=1;i<=n;i++){
    	int x=read();
    	d[x+200]++;//记录该数出现的次数，消除后面重复运算
	}
	for (int i=-200;i<=200;i++){
		if (!d[i+200]) continue;//如果这个数没有出现过则跳过
		for (int j=-200;j<i;j++){
			if (!d[j+200]) continue;//同上
			ans+=d[i+200]*d[j+200]*(i-j)*(i-j);
		}
	}
	cout<<ans<<endl;
   	return 0;
}

感谢！

回复

共 6 条回复，欢迎继续交流。

正在加载回复...