題意：

??? 給定一維上若干點xi，每個點有對應(yīng)的權(quán)值wi，求一個點的位置p，使得sigma? fabs(p-xi)^3*wi最小。

解題：

? 看了網(wǎng)上現(xiàn)有的所有博客，都是直接說是個凸函數(shù)，三分一下就好。求導(dǎo)好像也不直觀，也不知道具體是怎么證明的，姑且認為是個開口向上的二次函數(shù)（因為求的是最小值，且直觀上，p的位置肯定是在中間好），那么三分就可以求解了，需要注意的是，這題C++應(yīng)該是會T的，交G++才能過，然后向最近位取舍，應(yīng)該用%.0lf輸出。

?? 【三分性質(zhì)】

??????? 將區(qū)間三等分，取左等分點為lmid,右等分點為rmid，比如此題，二次函數(shù)開口向上，那么就算lmid的函數(shù)值為lv，rmid的函數(shù)值為rmid，比較lv和rv的值，假設(shè)最小值不在lmid和rmid之間，在兩側(cè)，那么lv，rv哪個更小，其對應(yīng)的等分點就更接近最值，故而舍棄大的那邊。倘若，最小值在lmid和rmid之間，那么無論舍棄哪一邊，都不會丟棄最值，同時達到逼近最值的效果，因為最值在何處，我們是不知道的，故而和第一種情況相統(tǒng)一，舍棄較大的一邊。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define eps 1e-8
using namespace std;
double x[50010],w[50010];
int n;
double cal(double y)
{
	double tmp,res=0.0;
	for(int i=0;ieps)
		{
			double lmid,rmid,lv,rv;
			lmid=(ri-le)/3+le;
			rmid=ri-(ri-le)/3;
            lv=cal(lmid);
			rv=cal(rmid);
			if(lv>rv)
				le=lmid;
			else
				ri=rmid;
		}
		printf("Case #%d: %.0lfn",i,cal(le));
	}
	return 0;
}