咕咕咕咕咕咕。
G - Infinite Knapsack
做法1 - 二分
假设第 \(i\) 个物品选了 \(x_i\) 个，\(x_i\)为非负整数，有
\[\lim_{x \to +\infin} \frac{f(x)}{x} = \frac{\sum_i c_i x_i}{\max(\sum_i a_i x_i, \sum_i b_i x_i)} \]所有情况中的最大值即为答案。这显然还不够优秀。
\(X\) 趋近于正无穷，相当于可以把给定物品不断等比细分， \(x_i\) 也可以是非负实数。为了简化问题，把所有物品转化成价值为 \(1\) 的物品，即重量为 \(\frac{a_i}{c_i}\) ，体积为 \(\frac{b_i}{c_i}\) ，价值为 \(1\) 。
考虑通过二分求解答案，每次检查对答案是否大于等于 \(y\)，即 \(\lim_{X \to +\infin} \frac{f(X)}{X} \ge y\) ，带入得
令 \(z = \frac{1}{y}\)，则有
\[\begin{aligned} \max (\sum_i a_i x_i, \sum_i b_i x_i) &\le z\sum_i x_i\\ \max (\sum_i (a_i - z) x_i, \sum_i (b_i - z) x_i) &\le 0 \end{aligned} \]然后分类讨论：
- \(a_i - z \le 0, b_i - z \le 0\)：存在这类物品即可行。
- \(a_i - z > 0, b_i - z > 0\)：这类物品属于无用物品。
- \(a_i - z < 0, b_i - z \ge 0\)
- \(a_i - z \ge 0, b_i - z < 0\)
现在只需要考虑后两类物品，不妨将其都放缩为 \((-1, B)\) 或者 \((A, -1)\) ，然后贪心只考虑 \(A\) 最小和 \(B\) 最小的物品。现在只需要看是否能构造出 \((x, y)\) 使得 \(\max(-x + yA, xB - y) \le 0\) ，解方程得只需 \(AB \le 1\)。
实现的时候可以直接二分 \(z\)，最后再求个倒数得到 \(y\)。
AC代码
// 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
// Author: Backlight
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define CPPIO \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
void Initialize();
void SolveCase(int Case);
int main(int argc, char* argv[]) {
CPPIO;
Initialize();
int T = 1;
// std::cin >> T;
for (int t = 1; t <= T; ++t)
SolveCase(t);
return 0;
}
void Initialize() {}
void SolveCase(int Case) {
int n;
std::cin >> n;
std::vector<std::array<double, 2>> p(n);
for (int i = 0; i < n; ++i) {
int a, b, c;
std::cin >> a >> b >> c;
p[i] = {1.0 * a / c, 1.0 * b / c};
}
auto check = [&](double x) {
double A = 1e18, B = 1e18;
for (int i = 0; i < n; ++i) {
double a = p[i][0] - x;
double b = p[i][1] - x;
if (a <= 0 && b <= 0)
return true;
if (a < 0)
B = std::min(B, b / (-a));
if (b < 0)
A = std::min(A, a / (-b));
}
if (A == 1e18 || B == 1e18)
return false;
return A * B <= 1;
};
const double eps = 1e-8;
double l = 0, r = 1e18, mid;
while (r - l >= eps) {
mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
std::cout << std::fixed << std::setprecision(12) << 1 / l << "\n";
}
做法2 - 凸包
同样的先把物品转化成价值为 \(1\) 的物品。然后，对于两个物品 \((a_i, b_i)\) 和 \((a_j, b_j)\) ，如果 \(a_i < a_j\) 且 \(b_i < b_j\) ，那么选 \((a_i, b_i)\) 肯定不如 \((a_j, b_j)\)。把 \((a_i, b_i)\) 看成二位平面上的点，则如果一个点的左下角有点，则这个点就不需要考虑。
求出点集的凸包，则只需要考虑下凸包上的点。
然后，由于 \(X\) 趋近于正无穷，物品可以无限细分，所以可以把下凸包上的线段也看成点，相当于用线段两个端点对应物品合成一个新的物品。然后根据前面的观察，不需要考虑 \(3\) 个及以上物品的合成，也不需要考虑不相邻的物品的合成。
然后就是模拟了。
代码咕咕咕。
Ex - Monster
To be solved。
标签：std,AtCoder,le,frac,Beginner,int,sum,275,物品 From： https://www.cnblogs.com/zengzk/p/16840354.html