HDU 4355
三分法
[cpp]
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 50010
double p[N],w[N];
int n;
double cal(double mid){
int i;
double ans=0;
for(i=1;i<=n;i++){
double err=fabs(mid-p[i]);
ans+=w[i]*err*err*err;
}
return ans;
}
int main(){
int t,T;
int i;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf %lf",&p[i],&w[i]);
double l=-1000000,r=1000000;
while(r-l>1e-4){
double ll=(l*2+r)/3;
double rr=(l+r*2)/3;
double ans1=cal(ll);
double ans2=cal(rr);
if(ans1>ans2)
l=ll;
else
r=rr;
}
printf("Case #%d: %.0lf\n",t,cal(l));
}
}
补充：软件开发 , C++ ,
