Comet OJ - Contest #8 B 支援城市
直接模拟 (O(n^2)) TLE ,把式子展开计算,(O(n))
[sum_{i = 1}^n {(w_i - w_x)^2} = sum_{i = 1}^n(w_i^2 - 2w_iw_x + w_x^2) = sum_{i = 1}^n w_i^2 - 2w_xsum_{i = 1}^n w_i + sum_{i = 1}^n w_x^2
]
将 $ sum_{i = 1}^n w_i^2$ 记作 (ss)
将 (sum_{i = 1}^n w_i) 记作 (s)
上述表达式简写成 : $ ss - 2w_xs + nw_x^2$
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll a[N],s,ss;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin >> n;
for(int i = 0;i < n; ++i){
cin >> a[i];
s += a[i];
ss += a[i] * a[i];
}
for(int i = 0;i < n; ++i){
cout << ss - 2 * a[i] * s + n * a[i] * a[i] <<' ';
}
return 0;
}