USACO 2017 January Contest, Platinum Problem 2. Building a Tall Barn

原題下載

USACO2017-JAN-P2

答案:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5+5;

ll n, k, a[MAXN];

ll ct(double x) {
ll tot = 0;
for (int i = 0; i < n; ++i)
// Using the quadratic formula to solve a[i]/(c(c+1)) >= x
tot += ll((sqrt(1 + 4*a[i]/x)-1)/2);
return tot;
}

int main() {
cin >> n >> k;
k -= n;

for (int i = 0; i < n; ++i)
cin >> a[i];

double lo = 0, hi = 1e18;
for (int i = 0; i < 200; ++i) {
double mid = (lo+hi)/2;
if (ct(mid) >= k)
lo = mid;
else
hi = mid;
}

double ans = 0;
ll tot = 0;

for (int i = 0; i < n; ++i) {
ll x = ll((sqrt(1 + 4*a[i]/lo)-1)/2);
ans += 1.0*a[i]/(x+1);
tot += x;
}

cout << (ll)round(ans - (k-tot)*lo) << endl;
}

以上就是關(guān)于【USACO 2017 January Contest, Platinum Problem 2. Building a Tall Barn】的解答，如需了解學校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

耗時一年備考 USACO 卻毫無收獲？一文教你找準最佳備考起步時間！

2026 NOAI國際AI奧賽中國站即將開考！賽事地址&日程已出！