很常规的一个题，刚开始想的是两重循环的暴力，然后发现一重循环的做法也十分好想，就是要先列出式子来找一下做法，然后就正常列式子，合并，化简。
在输入过程中记录所有数字的和和所有数字的平方和，然后枚举1到n的数字，当去掉每个数字时的答案，输出。。他的输出太格式化了，。
然后考场上最后得出来的式子是这样的：
式子没什么问题，交上去，，三十分。
随便看了看那些a掉的，，感觉他们写的式子都比较短吧，，
然后就想是不是化的还不够简，还真是，，，对于最后的答案式子，还能再化简。
把最后的*（n-1）乘进去，xba平均数可以抵消一部分，那么就又简单了！剩下tot-a[i]又正好是sum，所以答案就为：
那xba平均数的计算就没有必要了，，，就是又化简了一步，，就能a。。。。无语。
没完全化简之前有一些重复***作，而且也包含着小数，所以会出错。。。。所以要化简到底。。
很重要的一点是：计算方差是不一定要计算平均值的！
ac代码，时间复杂度O（n）：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
double xba;
int a[100002];
long long tot,sfang,sum,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
tot+=a[i];
sfang+=a[i]*a[i];
}
for(int i=1;i<=n;++i)
{
sum=tot-a[i];
xba=1.0*(tot-a[i])/(n-1);
ans=(sfang-a[i]*a[i])*(n-1)-sum*sum;
if(i==n)
{
printf("%lld\n",ans);
break;
}
printf("%lld ",ans);
}
return 0;
}
全部评论
(0) 回帖