NC25344. Help Me
描述
有一天Miss Quan出了一个题，给出一个长度为
听到这里，小伙伴们说这不是很简单吗，于是写出了下面的代码:
Miss Quan会心一笑，大家意识到事情并不简单，这个解法时间复杂度太高了，你能想出更好的计算Value的方法吗？只需要输出Value的值即可。
输入描述
第一行输入一个整数代表共有组数据
。
对于每组测试用例第一行输入一个整数
第二行输入
个数
输出描述
对于每组数据，输出一行，一个整数代表
的值.
示例1
输入:
2 3 1 4 2 2 10 20
输出:
14 100
示例2
输入:
1 4 5 6 8 7
输出:
20
C++14(g++5.4) 解法, 执行用时: 73ms, 内存消耗: 712K, 提交时间: 2020-03-11 19:06:16
#include<bits/stdc++.h>
using namespace std;
long long a[100010];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
long long sum=0,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum=sum+a[i];
ans=ans+a[i]*a[i];
}
cout<<n*ans-sum*sum<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 57ms, 内存消耗: 504K, 提交时间: 2019-04-25 15:24:22
#include<cstdio>
int T,n,m;
long long x,y;
int main(){
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d",&n);x=y=0;
for(int i=1;i<=n;i++){
scanf("%d",&m);
x=x+m*m;
y=y+m;
}
printf("%lld\n",1ll*n*x-y*y);
}
}