本文共 1041 字,大约阅读时间需要 3 分钟。
题意:给你n个行星,移动k个行星,绕他们的质心速度变得更大,使得这些行星的速度变得更大,那么就要使得
I的值更小即可,
#include#include #include #include using namespace std;double zb[70100];double sum[70005];double s[70005];int main(){ int t,n,m; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%lf",&s[i]); if(m >= n - 1) {printf("0\n");continue;} sort(s+1,s+n+1); zb[0] = 0;sum[0] = 0; for(int i = 1;i <= n;i++){ zb[i] = zb[i-1] + s[i];//预处理前n项和; sum[i] = sum[i-1] + s[i]*s[i];//预处理前n项平方和; } double zx1 = zb[n]/(n-m); double _min = sum[n] + (n-m) * zx1 * zx1 - 2 * zx1 * zb[n];//注意不移动的时候他的I值 for(int i = n-m;i <= n ;i++)//苦逼的边界无限的WA { double tmp = zb[i] - zb[i-n+m]; double r = tmp/(n-m); double k = sum[i] - sum[i-n+m]; double ret = k + (n-m) * r * r - 2 * r * tmp; _min = min(ret,_min); } printf("%.10lf\n",_min); } return 0;}
转载地址:http://ucsgi.baihongyu.com/