题目大意：有n个精灵位于一维坐标轴上， 每个精灵有一个权值w， 每个精灵走到另一个位置耗费能量S^3 * w。（s是两点间距离）。现在精灵要聚会， 求选取一点，使所有精灵到这点浪费能量之和最小。  

分析：设这点的位置是x，精灵位置是pi，则浪费能量值和f = sigma[(pi-x)^3*wi].其中x是变量. 通过对这个函数求二次导可以发现，这个函数是一个下凸函数.可以用

三分做.   具体的三分方法如图： 凸函数：   凹函数：     三分求凸函数极值模板：  

//如果一个解函数的二次导恒>0(or <0)，则该函数为凸函数.//精度模板const double eps = 1e-6;bool dy(double x,double y)  {   return x > y + eps;} 		// x > ybool xy(double x,double y)  {   return x < y - eps;} 		// x < ybool dyd(double x,double y) {   return x > y - eps;} 		// x >= ybool xyd(double x,double y) {   return x < y + eps;}     	// x <= ybool dd(double x,double y)  {   return fabs( x - y ) < eps;}    // x == ydouble cal(double pos){    /* 根据题目的意思计算 */}double solve(double left, double right){    while(xy(left, right)){        double mid = DMID(left, right);        double midmid = DMID(mid, right);        double mid_area = cal(mid);        double midmid_area = cal(midmid);        if (xyd(mid_area, midmid_area))     //下凸函数，上凸函数用dyd(mid_area, midmid_area)            right = midmid;        else            left = mid;    }    return left;}

  HDU 4355 代码：  

#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)#define DMID(x,y) ((x+y)/2)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int N = 50002;double x[N], w[N];int n;//二分精度模板const double eps = 1e-6;bool dy(double x,double y)  {   return x > y + eps;} 		// x > ybool xy(double x,double y)  {   return x < y - eps;} 		// x < ybool dyd(double x,double y) {   return x > y - eps;} 		// x >= ybool xyd(double x,double y) {   return x < y + eps;}     	// x <= ybool dd(double x,double y)  {   return fabs( x - y ) < eps;}    // x == ydouble cal(double pos){    /* 根据题目的意思计算 */    double res = 0.0;    for (int i = 0; i < n; i ++){        res += abs(pos - x[i]) * abs(pos - x[i]) * abs(pos - x[i]) * w[i];    }    return res;}double solve(double left, double right){    while(xy(left, right)){        double mid = DMID(left, right);        double midmid = DMID(mid, right);        double mid_area = cal(mid);        double midmid_area = cal(midmid);        if (xyd(mid_area, midmid_area))     //下凸函数，上凸函数dyd(mid_area, midmid_area)            right = midmid;        else            left = mid;    }    return left;}int main(){    int t;    scanf("%d", &t);    for (int caseo = 1; caseo <= t; caseo ++){        scanf("%d", &n);        double low = -1000000, high = 1000000;        for (int i = 0; i < n; i ++){            scanf("%lf %lf", &x[i], &w[i]);            low = min(low, x[i]);            high = max(high, x[i]);        }        printf("Case #%d: %.0f\n", caseo, (cal(solve(low, high))));    }	return 0;}