事实证明，ABC389e的实现可能没那么难

写二分时溢出是一个很大的困扰。但是如果你善用浮点数的超大值域，可能可以简单的解决这个问题。

如果浮点数的大小没有爆longlong，那么longdouble的精度就是足够的。如果爆了longlong，那么就一定比m更大，精度也就无所谓了。

理论上来说，longdouble的精度是足够存下longlong范围内的所有数的，而double不行。但是经过实践，用longdouble或double都能通过本题。

CPP

#include <bits/stdc++.h>

using namespace std;
int n;
long long m;
array<int, 200005> p;

bool check(long long x) {
    long double tot = 0;

    for (int i = 1; i <= n; ++i) {
        long long k = floor(((long double) x / p[i] + 1) / 2);

        tot += 1.0L * k * k * p[i];
        if (tot > m) {
            return false;
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    long long l = 0, r = 1e18;
    while (l < r) {
        long long mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        long long k = floor(((long double) l / p[i] + 1) / 2);

        ans += k;
        m -= k * k * p[i];
    }
    ans += m / (l + 1);

    cout << ans;
    return 0;
}

事实证明，ABC389e的实现可能没那么难

讨论操作

回复

相关推荐

事实证明，ABC389e的实现可能没那么难