题意:Markdown

思路:

纯看题解的题QAQ

首先可以把题目中的式子化成这样Markdown

所以可以把每个(ti-T)分成两类,一类正,一类负。

用贪心的思想,可以发现有一半必须全选,另一半选最靠近T的那些,因为ti-T越小,xi越大。

所以排序之后贪心就可以了。

涨姿势了原来这题目是这么做的。

可是这道题我debug了很久QAQ到现在我也不知道之前WA的写法错哪儿了 我只不过把之前负的的计数改成了正的 就AC了 很奇怪 不知道错哪儿了 很迷QAQ

代码:

typedef long long ll;
struct node
{
    ll a,t;
} nd[200010];
bool cmp1(node x,node y)
{
    return x.t<y.t;
}
bool cmp2(node x,node y)
{
    return x.t>y.t;
}
int main()
{
    int n;
    ll T;
    scanf("%d%lld",&n,&T);
    for(int i=0; i<n; i++)
        scanf("%lld",&nd[i].a);
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&nd[i].t);
        nd[i].t-=T;
    }
    double ansn=0,ansp=0;
    ll stn=0,stp=0;
    for(int i=0; i<n; i++)
    {
        if(nd[i].t<0){stn-=nd[i].a*nd[i].t;ansn+=1.0*nd[i].a;}
        else {stp+=nd[i].a*nd[i].t;ansp+=1.0*nd[i].a;}
    }
    //printf("%lld %lld\n",stn,stp);
    if(stn<stp)
    {
        sort(nd,nd+n,cmp1);//把负的当少的
        for(int i=0; i<n; i++)
        {
            if(nd[i].t>=0)
            {
                if(stn-1.0*nd[i].a*nd[i].t>=0)
                {
                    stn-=nd[i].a*nd[i].t;
                    ansn+=1.0*nd[i].a;
                }
                else
                {
                    ansn+=stn/(1.0*nd[i].t);
                    stn=0;
                    break;
                }
            }
        }
        printf("%.15f\n",ansn);
    }
    else
    {
        sort(nd,nd+n,cmp2);//把正的当少的
        for(int i=0; i<n; i++)
        {
            if(nd[i].t<0)
            {
                if(stp-1.0*nd[i].a*(-nd[i].t)>=0)
                {
                    stp-=nd[i].a*(-nd[i].t);
                    ansp+=1.0*nd[i].a;
                }
                else
                {
                    ansp+=stp/(-1.0*nd[i].t);
                    stp=0;
                    break;
                }
            }
        }
        printf("%.15f\n",ansp);
    }
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

三分查找 Previous
bzoj1853 容斥原理+dfs Next