zcmimi's blog
查看原题

点击跳转

思路还算挺神奇的

题意:

\sum C_i=k,要让\sum \dfrac{A_i}{C_i}最小

T_i=\dfrac{A_i}{C_i}

假设我们每次要给一个C_i加一,那么\Delta T_i=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1},

我们要让\Delta T_i尽可能大

这样一直加一到最后,会让所有\Delta T_i趋近于相同

\begin{aligned} \Delta T_i &=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1}\\ &=\dfrac{A_i}{C_i(C_i+1)}\\ &=\dfrac{A_i}{C_i^2+C_i} \end{aligned}\\ C_i^2+C_i-\dfrac{A_i}{\Delta T_i}=0\\ C_i=\dfrac{-1+\sqrt{1+\frac{4A_i}{\Delta T_i}}}2

由于\Delta T_i是单调的,\Delta T_i越小,答案越小

所以我们可以二分\Delta T_i,并倒推得出C_i

#include<bits/stdc++.h>
const int N=100011;
typedef long long ll;
typedef double db;
int n;ll k,sum,a[N];db Ans;
bool chk(db t,bool typ=0){
    ll s=0;
    for(int i=1;i<=n;++i){
        ll c=ceil(sqrt(0.25+a[i]/t)-0.5);
        s+=c;
        if(s>k)return 0;
        if(typ)Ans+=(db)a[i]/c;
    }
    if(typ)sum=s;
    return 1;
}
int main(){
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i)scanf("%lld",a+i);
    db l=1e-10,r=1e10,eps=1e-10,ans;
    while(r-l>=eps){
        db m=(l+r)*0.5;
        if(chk(m))r=ans=m;
        else l=m;
    }
    chk(ans,1);
    printf("%lld\n",ll(Ans-(k-sum)*ans+0.5));
}
LG 3606 [USACO17JAN]Building a Tall Barn P
comment评论
Search
search