1 条题解

  • 2
    @ 2025-6-5 20:42:34

    二分的,坑点是 k*s<= 1E18要考虑

    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    // bool check(const vector<int> &a, const vector<int> &b, const vector<int> &c, int k)
    // {
    //     int mx = 1e18;
    //     int mi = -1e18;
    //     for (int i = 0; i < a.size(); ++i)
    //     {
    //         int s = b[i] + c[i];
    //         mi = min(mi, a[i] - k * s);
    //         mx = min(mx, a[i] + k * s);
    //     }
    //     return mx >= mi;
    // }
    bool check(const vector<int> &a, const vector<int> &b, const vector<int> &c, int k)
    {
        int l = -1E18;
        int r = 1E18;
        for (int i = 0; i < a.size(); ++i)
        {
            int s = b[i] + c[i];
            if (k <= 1E18 / s)
            {
                int d = k * s;
                int lm = a[i] - d;
                int rm = a[i] + d;
                l = max(l, lm);
                r = min(r, rm);
            }
        }
        return l <= r;
    }
    void solve()
    {
        int n;
        cin >> n;
        vector<int> a(n), b(n), c(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        for (int i = 0; i < n; ++i)
            cin >> b[i];
        for (int i = 0; i < n; ++i)
            cin >> c[i];
        int l = 0, r = 1e18;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (check(a, b, c, mid))
            {
                r = mid;
            }
            else
                l = mid+1;
        }
        cout << l << '\n';
    }
    signed main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        // cin >> t;
        while (t--)
            solve();
    }
    

    信息

    ID
    1081
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    121
    已通过
    12
    上传者