首页 > 代码库 > hdu 5073 Galaxy（14鞍山区域赛 D） 二分 + 递推
hdu 5073 Galaxy（14鞍山区域赛 D） 二分 + 递推
题意：给定你一条直线，直线上面有n个点，你可以移动k个点，求所有点到重心距离的平方和最小值为多少。
解题思路：这里可以知道 保持一段不移动然后把所有的点都移动到这一段的重心才是最优解，那我们很容易想到枚举这一段的端点，但是如果枚举端点，时间复杂度会高达
n^2,所以我们要知道区间之间的关系，假设 lsum ，rsum ,lans,rans ,分别为 重心左右的 距离和 和重心左右的平方和，然后每次移动找重心位置，再算 这四个值之间的递推关系就行了。
解题代码：
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月22日 星期三 13时26分25秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 51005 26 #define eps 1e-8 27 using namespace std; 28 double a[maxn]; 29 int site[maxn]; 30 double zx[maxn]; 31 int LN; 32 int find(double x , int l , int r) 33 { 34 35 while(l <= r ) 36 { 37 int m = (l + r)/2; 38 if(a[m] > x) 39 r = m - 1; 40 else 41 l = m + 1; 42 } 43 return r; 44 } 45 int main(){ 46 int t; 47 scanf("%d",&t); 48 while(t--) 49 { 50 int n , k ; 51 scanf("%d %d",&n,&k); 52 for(int i = 1;i <= n;i ++) 53 { 54 scanf("%lf",&a[i]); 55 } 56 sort(a+1,a+1+n); 57 if(k >= n) 58 { 59 printf("0.00000000000\n"); 60 continue; 61 } 62 LN = n - k ; 63 double sum = 0 ; 64 double lans,rans,lsum,rsum; 65 lans = rans = lsum = rsum = 0 ; 66 67 for(int i = 1;i <= LN;i ++) 68 { 69 sum += a[i]; 70 } 71 zx[1] = sum / LN; 72 site[1] = find(zx[1],1,1 + LN-1); 73 for(int i = 1;i <= LN;i ++) 74 { 75 double tt = fabs(zx[1] - a[i]); 76 if(a[i] <= zx[1]) 77 { 78 lsum += tt; 79 lans += tt * tt; 80 }else { 81 rsum += tt; 82 rans += tt * tt; 83 } 84 } 85 double mi = lans + rans; 86 for(int i = 2;i <= k + 1;i ++) 87 { 88 sum -= a[i-1]; 89 sum += a[i + LN -1]; 90 zx[i] = sum/LN; 91 site[i] = find(zx[i],i,i + LN -1); 92 double dis = zx[i] - zx[i-1] ; 93 lsum -= fabs(a[i-1] - zx[i-1]); 94 lans -= fabs(zx[i-1] -a[i-1]) * fabs(zx[i-1] -a[i-1]); 95 lans += lsum * dis * 2 + dis *dis * (site[i-1] - i + 1); 96 lsum += dis * (site[i-1] - i + 1); 97 for(int j = site[i-1] + 1;j <= site[i];j ++) 98 { 99 double tt = fabs(a[j] - zx[i]);100 double tt1 = fabs(a[j] - zx[i-1]);101 lsum += tt; 102 lans += tt*tt;103 rsum -= tt1;104 rans -= tt1 * tt1;105 }106 // printf("%lf\n",rsum);107 rans += dis * dis *(i-1 + LN - 1 - site[i]) - rsum * dis * 2;108 rans += fabs(zx[i] - a[i+LN-1]) * fabs(zx[i] - a[i+LN-1]) ;109 rsum += fabs(zx[i] - a[i+LN-1]) - dis *(i-1+LN-1-site[i]);110 //printf("%lf\n",rsum);111 //printf("%lf %lf %lf %lf %lf\n",lsum,rsum,lans,rans,zx[i]);112 if(rans + lans < mi)113 mi = rans + lans;114 }115 printf("%.10lf\n",mi);116 117 }118 return 0;119 }
hdu 5073 Galaxy（14鞍山区域赛 D） 二分 + 递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。