1 条题解
-
2
二分的,坑点是 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(); }
- 1
信息
- ID
- 1081
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 121
- 已通过
- 12
- 上传者