原问题等价于:
给定 \(a_i = \frac{A_i}{C_i}, b_i = \frac{B_i}{C_i}\),要求 \(\sum\limits_{i = 1}^n x_i = 1\),\(x_i\) 为非负实数,求 \(\max(\sum\limits_{i = 1}^n a_i x_i, \sum\limits_{i = 1}^n b_i x_i)\) 的最小值。
考虑二分。设当前二分到 \(mid\),check 等价于:
给定 \(a_i = \frac{A_i}{C_i} - mid, b_i = \frac{B_i}{C_i} - mid\),要求 \(\sum\limits_{i = 1}^n x_i = 1\),\(x_i\) 为非负实数,问是否能使 \(\sum\limits_{i = 1}^n a_i x_i \le 0 \land \sum\limits_{i = 1}^n b_i x_i \le 0\)。
考虑若存在 \(i\) 使得 \(a_i \le 0 \land b_i \le 0\),那么就可行。
否则,我们找到 \(a_i < 0, b_i \ge 0\) 且 \(\frac{b_i}{-a_i}\) 最小的 \(i\),\(a_j \ge 0, b_j < 0\) 且 \(\frac{a_j}{-b_j}\) 最小的 \(j\),那么除了 \(i, j\) 以外,它的 \(x\) 值都等于 \(0\)。因为我们肯定想,选了其中一个属性 \(< 0\) 的元素,对另一种元素造成的影响尽量小。
那么现在就是问是否存在一个非负实数 \(x\) 满足:
- \(a_i x + a_j (1 - x) \le 0\)
- \(b_i x + b_j (1 - x) \le 0\)
这个就是一个一元一次不等式,判断下界是否小于等于上界即可。
code
// Problem: G - Infinite Knapsack
// Contest: AtCoder - AtCoder Beginner Contest 275
// URL: https://atcoder.jp/contests/abc275/tasks/abc275_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n;
ldb a[maxn], b[maxn], c[maxn], d[maxn];
inline bool check(ldb x) {
for (int i = 1; i <= n; ++i) {
c[i] = a[i] - x;
d[i] = b[i] - x;
if (c[i] <= 0 && d[i] <= 0) {
return 1;
}
}
ldb mn1 = 1e18, mn2 = 1e18;
int p = -1, q = -1;
for (int i = 1; i <= n; ++i) {
if (c[i] < 0 && -d[i] / c[i] < mn1) {
mn1 = -d[i] / c[i];
p = i;
}
if (d[i] < 0 && -c[i] / d[i] < mn2) {
mn2 = -c[i] / d[i];
q = i;
}
}
if (p == -1 || q == -1) {
return 0;
}
return c[q] / (c[q] - c[p]) <= d[q] / (d[q] - d[p]);
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%Lf%Lf%Lf", &a[i], &b[i], &c[i]);
a[i] /= c[i];
b[i] /= c[i];
}
ldb l = 0, r = 11;
while (r - l > 1e-8) {
ldb mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
printf("%.10Lf\n", 1 / l);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner Infinite Knapsack AtCoder Contestbeginner infinite knapsack atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 310