传送门 : UESTC 375
code:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef double ld; const int N = 1010; int n; int data[N], sum[N], sum2[N]; ld tmp[N], aver[N]; ld cal(int x){ aver[x] = (ld)sum[x] / x; return (ld)(sum[n] - sum[x]) / (n - x) - aver[x]; } int main(){ //freopen("in.txt", "r", stdin); int t; scanf("%d", &t); for(int cas = 1; cas <= t; ++cas){ scanf("%d", &n); sum[0] = 0; sum2[0] = 0; for(int i = 1; i <= n; ++i) scanf("%d", data + i); sort(data + 1, data + n + 1); for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + data[i], sum2[i] = sum2[i - 1] + data[i] * data[i]; for(int i = 1; i < n; ++i) tmp[i] = cal(i); ld mx = -1e10; for(int i = 1; i < n; ++i) mx = max(mx, n * tmp[i] * tmp[i] - sum[i] * aver[i] - (sum[n] - sum[i]) * (aver[i] + tmp[i])); printf("Case #%d: %.6lf\n", cas, mx + sum2[n]); } return 0; }