思路：三分法求f(x)极值。
f(x)是指位置为x时的愤怒值之和，是一个三次函数，且存在极值点使f(x)最小。
code：
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
#define INF 2147483647
#define cls(x) memset(x,0,sizeof(x))
#define rise(i,a,b) for(int i = a ; i <= b ; i++)
using namespace std;
const double eps(1e-8);
typedef long long lint;
const int maxn = 500000 + 5;
double x[maxn];
double w[maxn];
int n;
double f(double pos){
double sum = 0.0;
for(int i = 1 ; i <= n ; i++){
sum += (double)pow(abs(pos - x[i]) , 3) * w[i];
}
return sum;
}
double ts(double L , double R){
double ans = -1;
for(int i = 1 ; i < 30 ; i++){
double mid1 = (L+R)/2.0;
double mid2 = (mid1 + R)/2.0;
if(f(mid1) >= f(mid2))
L = mid1;
else
R = mid2;
}
ans = L;
return ans;
}
int main(){
// freopen("input.txt","r",stdin);
int t ; cin >> t; int kase = 1;
while(t--){
cin >> n;
double left = 1e7 , right = -1e7;
for(int i = 1 ; i <= n ; i++){
scanf("%lf%lf",&x[i],&w[i]);
left = min(left , x[i]);
right = max(right , x[i]);
}
printf("Case #%d: %.0f\n",kase++ , f(ts(left,right)));
}
return 0;
}
版权声明：博主表示授权一切转载：）
HDU 4355 Party All the Time（三分法搜索）
原文：http://blog.csdn.net/qq_15714857/article/details/47190081