197
HDU 4355 三分
題意：在一維數軸上給出點，每個點到求的那一點的距離為s，那麼他的不高興值就是s^3*w[i]，求導可以得出類似一個凹的圖像，三分法求出的最小值。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-4
int n,t;
double x[50005],w[50005];
double getans(double s)
{
double ans=0;
for(int i=0; i<n; i++)
{
double s1=fabs(s-x[i]);
ans+=s1*s1*s1*w[i];
}
return ans;
}
int main()
{
int ca=0;
scanf("%d",&t);
while(t--)
{
double l,r;
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%lf%lf",&x[i],&w[i]);
l=x[0],r=x[n-1];
double mid1,mid2;
while(r-l>1e-4)
{
mid1=l+(r-l)/3,mid2=r-(r-l)/3;
if(getans(mid1)>getans(mid2))
l=mid1+eps;
else
r=mid2-eps;
}
printf("Case #%d: %.0f\n",++ca,getans(l));
}
return 0;
}
最後更新：2017-04-03 16:48:36