HDU 4355 Party All the Time（三分）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：坐标轴上有一些点，每个点有权值，找出一个位置，所有点到这个点的距离的三次方乘以权值的和最小。

http://acm.hdu.edu.cn/showproblem.php?pid=4355

根据题意如果中心为X0,Y0，那么结果为sigma(|Xi-X0|^3*W)。

这是一个凸函数，因为它的二次导大于0，适用于三分

练习赛的时候只听过三分，就瞎着YY了，不过最后还是爆ULL了，跪，没想到最后是用double直接处理

#include<iostream>#include<cstdio>#include<ctime>#include<cstring>#include<cmath>#include<algorithm>#include<cstdlib>#include<vector>#define C    240#define TIME 10#define eps 1e-7#define inf 1<<25#define LL unsigned long longusing namespace std;struct Node{    double x;    double w;}a[50005];int n;double cal(double pos){    double sum=0;    for(int i=0;i<n;i++)        sum+=fabs(a[i].x-pos)*fabs(a[i].x-pos)*fabs(a[i].x-pos)*a[i].w;    return sum;}int main(){    int t,cas=0;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        double low=1000000,high=-1000000;        for(int i=0;i<n;i++){            scanf("%lf%lf",&a[i].x,&a[i].w);            low=min(low,a[i].x);            high=max(high,a[i].x);        }        printf("Case #%d: ",++cas);        double midd,mid=(low+high)/2;        while(fabs(high-low)>=eps){            mid=(low+high)/2;            midd=(mid+high)/2;            if(cal(mid)+eps<cal(midd))                high=midd;            else                low=mid;        }        double dist=cal(low);        printf("%.0f\n",dist);    }    return 0;}

1楼shuimu12345678昨天 15:28

为什么适用于三分呢？

Re: ACM_cxlove昨天 15:52

回复shuimu12345678n对于这题，确切的说是凹函数，不过都一样

Re: ACM_cxlove昨天 16:36

回复shuimu12345678n三分求的是凸函数的最值n就是二阶导恒非正或恒非负的情况n你可以把原式求两次导