題目鏈接：HDU 4355

題面：

Party All the Time Time Limit: 6000/2000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5266????Accepted Submission(s): 1625


Problem Description In the Dark forest, there is a Fairy kingdom where all the spirits will go together and Celebrate the harvest every year. But there is one thing you may not know that they hate walking so much that they would prefer to stay at home if they need to walk a long way.According to our observation,a spirit weighing W will increase its unhappyness for S³*W units if it walks a distance of S kilometers.
Now give you every spirit's weight and location,find the best place to celebrate the harvest which make the sum of unhappyness of every spirit the least. ?
Input The first line of the input is the number T(T<=20), which is the number of cases followed. The first line of each case consists of one integer N(1<=N<=50000), indicating the number of spirits. Then comes N lines in the order that x_[i]<=x_[i+1] for all i(1<=ii,W_i, representing the location and the weight of the i-th spirit. ( |x_i|<=10⁶, 0i<15 ) ?
Output For each test case, please output a line which is "Case #X: Y", X means the number of the test case and Y means the minimum sum of unhappyness which is rounded to the nearest integer. ?
Sample Input

1 4 0.6 5 3.9 10 5.1 7 8.4 10 ?
Sample Output

Case #1: 832 ?
Author Enterpaise@UESTC_Goldfinger ?
Source 2012 Multi-University Training Contest 6

題意：

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

解題：

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

?? 【三分性質】

??????? 將區(qū)間三等分，取左等分點為lmid,右等分點為rmid，比如此題，二次函數開口向上，那么就算lmid的函數值為lv，rmid的函數值為rmid，比較lv和rv的值，假設最小值不在lmid和rmid之間，在兩側，那么lv，rv哪個更小，其對應的等分點就更接近最值，故而舍棄大的那邊。倘若，最小值在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;
}