首页 > 代码库 > hdu 2014鞍山赛区 5073 Galaxy

hdu 2014鞍山赛区 5073 Galaxy

2024-07-28 17:09:20   221人阅读

题意：就是给你 n 个数，代表n个星球的位置，每一个星球的重量都为 1 ！
开始的时候每一个星球都绕着质心转动，那么质心的位置就是所有的星球的位置之和 / 星球的个数
现在让你移动 k 个星球到任意位置（多个星球可以在同一个位置并且所有的星球在同一直线上）
移动之后那么它们质心的位置就可能发生变化，求 I = sum(di^2) di （表示第i个星球到达质心的距离）最小！

设d为n-k个星球的质心位置，如果I值最小，那么移动的k个星球一定都放在另外n-k个星球的质心上，
并且这n-k个星球一定是连续的！越密集方差越小嘛.....
x1, x2, x3, x4,....x(n-k)表示余下n-k个星球的位置
思路：I = sum(di^2) = (x1-d)^2 + (x2-d)^2 + (x3-d)^2 ....
= sum(xi^2) + (n-k)*d*d - 2*d*sum(xi);

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define N 50050 6 using namespace std; 7 double num[N]; 8 double s1[N], s2[N]; 9 int main(){10     int n, t, k;11     scanf("%d", &t);12     while(t--){13         scanf("%d%d", &n, &k);14         for(int i=1; i<=n; ++i)15             scanf("%lf", &num[i]);16         sort(num+1, num+n+1);//对星球的位置排一下序 17         for(int i=1; i<=n; ++i)//分别计算前缀num[i] 的和 以及 num[i]^2的和 18             s1[i] = s1[i-1] + num[i], s2[i] = s2[i-1] + num[i]*num[i];19         int m = n-k;20         double ans = 1000000000000000000.0;//ans要足够大.... 最好不用long long，可能会超.... 21         for(int i=1; m && i+m-1<=n; ++i){22             int j = i+m-1;23             double d = (s1[j] - s1[i-1])/m;24             double tmp = s2[j] - s2[i-1] - 2*d*(s1[j] - s1[i-1]) + m*d*d;25             if(ans > tmp) ans = tmp;26         }27         if(n == k) ans = 0.0; 28         printf("%.9lf\n", ans);29     }30     return 0;31 }
View Code

 

hdu 2014鞍山赛区 5073 Galaxy


联系
我们