二分

HDU 4355 Party All the Time

暑假集训选拔马上就要开始了

挺虚的,就临时抱一下佛脚

把以前没有写的周练补一下,从最开始补起,也就是二分三分

没想到一下子就A了,说明还是有点长进的,哈哈,可喜可贺,可喜可贺

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-6

using namespace std;

inline double cal(double a,double b)
{
    if(a<0) a=-a;
    return a*a*a*b;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        int n;
        double x[50100],w[50100],l=1000000,r=-1000000,mid,midmid,ans=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&x[i],&w[i]);
            l=min(l,x[i]);
            r=max(r,x[i]);
        }
        while(eps+l<=r)
        {
            mid=(l+r)/2;
            midmid=(l+mid)/2;
            double msum=0,mmsum=0;
            for(int i=0;i<n;i++)
            {
                msum+=cal(mid-x[i],w[i]);
                mmsum+=cal(midmid-x[i],w[i]);
            }
            if(msum+eps<mmsum) l=midmid;
            else r=mid;
            ans=min(msum,mmsum);
        }
        printf("Case #%d: %.0f\n",k,ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注