[USACO 2017 Jan P]Building a Tall Barn

Farmer John is building a brand new, N-story barn, with the help of his K cows ( $1 \leq N \leq K \leq 10^{12}$ and $N \leq 10^5$ ). To build it as quickly as possible, he needs your help to figure out how to allocate work among the cows.

Each cow must be assigned to work on exactly one specific floor out of the N total floors in the barn, and each floor must have at least one cow assigned to it. The ith floor requires $a_i$ units of total work, and each cow completes one unit of work per hour, so if c cows work on floor i, it will be completed in $\frac{a_i}{c}$ units of time. For safety reasons, floor i must be completed before construction can begin on floor i+1.

Please compute the minimum total time in which the barn can be completed, if the cows are allocated to work on floors in an optimal fashion. Output this number rounded to the nearest integer; it is guaranteed that the solution will be more than 0.1 from the boundary between two integers.

#include<bits/stdc++.h> #define Ll long long using namespace std; const Ll N=1e5+5; double a[N],l,r,mid,ans,T; Ll x,k,sum,n; bool check(double t){ Ll sum=0; for(Ll i=1;i<=n;i++){ double c=(sqrt(1+4*a[i]/t)-1)/2.; Ll v=ceil(c); sum+=v; if(sum>k)return 0; }return 1; } int main() { scanf("%lld%lld",&n,&k); for(Ll i=1;i<=n;i++)scanf("%lld",&x),a[i]=x; l=1e-9,r=12; while(r-l>1e-9){ mid=(l+r)/2.; if(check(mid))r=mid;else l=mid; } for(Ll i=1;i<=n;i++){ double c=(sqrt(1+4*a[i]/r)-1)/2.; Ll v=ceil(c); sum+=v; ans+=a[i]/v; } printf("%.0lf",ans-(k-sum)*r); }

详情