首页 > 代码库 > Hdu 5073 Galaxy 精度问题

Hdu 5073 Galaxy 精度问题

2024-07-28 17:01:24   218人阅读

 

　　思路： 其实求解很简单直接说解法，移动K个后 上下的角动量最小，能肯定是相连的（n-k）个，至于为什么 你自己好好想想（easy）；

　　　　　对于一些等质量的质点中心在 所在位置和除以点的个数

　　　　　average=sum[l,l+(n-k)-1]/(n-k);

　　　　　 一个点的值： (pi-average)* (pi-average)

　　　　　 也就是 pi^2+avery^2 - 2*pi*average  

　　　　　 多个点相加也就是 ∑pi^2+(n-k)*sum*sum/(n-k)/(n-k)   -  2*∑pi*sum/(n-k);

　　　　　　　　　　　　=   ∑pi^2+(n-k)*sum*sum/(n-k)/(n-k)   -  2*sum*sum/(n-k);

　　　　　　　　　　　　=   ∑pi^2   -  sum*sum/(n-k);

　　　　　所以要处理一下 ”普通和“，“平方和” 就好了

　　　　　但是这个卡精度：我的做法  每次比较   （n-k）*∑pi^2   -  sum*sum

　　　　　剩下最小的 再除以（n-k） 就好了

代码.cpp

 

 1 #include <string> 2 #include <cstring> 3 #include <iostream> 4 #include <cstdio> 5 #include <algorithm> 6 using namespace std; 7 typedef long long ll; 8 int n,k,d[50005]; 9 ll sum[50005];10 ll getsum(int i,int j)11 {12     if(i)return sum[j-1]-sum[i-1];13     else return sum[j-1];14 }15 16 int main()17 {18     int t;19     scanf("%d",&t);20     while(t--)21     {22         memset(d,0,sizeof d);23         memset(sum,0,sizeof sum);24         scanf("%d%d",&n,&k);25         for(int i=0;i<n;i++)26             scanf("%d",&d[i]);27         sort(d,d+n);28         for(int i=0;i<n;i++)29             if(i) sum[i]=sum[i-1]+(ll)d[i];30             else sum[i]=(ll)d[i];31         double messc=0.0,minv=0.0,now=0.0;32         for(int j=0;j<=k;j++)33         {34             ll nows=getsum(j,n-(k-j));35             messc=(double)nows/(double)(n-k);36             now=0.0;37             for(int i=j;i<=(n-1)-(k-j);i++)38             {39                 double dis=(double)d[i]-messc;40                 now+=(dis*dis);41                 if(j && now>=minv) break;42             }43             if(!j)minv=now;44             else if(now<minv) minv=now;45         }46         printf("%.12f\n",minv);47     }48     return 0;49 }

 

Hdu 5073 Galaxy 精度问题


联系
我们