E题意:
制作产品,有n道工序。
每道工序有两种设备,单价 pi和 qi一天可做 ai和bi的产品。
最终的生产效率是所有工序的产品数量的最小值。
现有 x元,问生产效率的最大值。
随着效率的增大,所需要的钱变多。所以效率和需要的钱之间是单调的。可以二分。
那么问题变成 给定效率 判断所需要的最少的钱 是否小于等于X 。
那么对于给定的效率怎样找到 所 需要的最少的钱
先贪心的想,我们肯定要选择性价比高的机器(用较少的钱做更多的工作).如果刚好这些机器的效率是mid,那么这是最优的。如果效率>mid ,那么就有可能存在将几个a替换为b ,然后效率为MId,花费的更少。
可以枚举替换上去几个b 。(性价比低的那一个不会选很多。然后因为a b 很小,X很大,可以枚举性价比低的次数)
这个每次check 是接近O(n)的复杂度。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
struct node
{int a, p, b, q; // 产量价格
};
void solve()
{int n, x;cin >> n >> x;vector<node> v(n);for (int i = 0; i < n; i++){cin >> v[i].a >> v[i].p >> v[i].b >> v[i].q;// 性价比 ,让 a 是高性价比的东西double t1 = (1.0 * v[i].a) / (1.0 * v[i].p);double t2 = (1.0 * v[i].b) / (1.0 * v[i].q);if (t1 < t2){swap(v[i].a, v[i].b);swap(v[i].p, v[i].q);}}// 产生mid 的效益,判断花销是否超过xauto check = [&](int mid) -> bool{int ans = 0;for (auto t : v){int sum = 0;int num = (mid + t.a - 1) / t.a;sum = num * t.p;if (mid % t.a == 0){ans += sum;continue;}// 用 b 替换 a ,枚举替换的b 的数量for (int i = 1; i <= 100; i++){int le = mid - i * t.b;int tt = i * t.q;tt += t.p * ((le + t.a - 1) / t.a);sum = min(sum, tt);}ans+=sum;}return ans <= x;};int l = 0, r = 1e9+10;while (l <= r){int mid = l + r >> 1;if (check(mid))l = mid + 1;elser = mid - 1;}cout << l - 1 << "\n";
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin>>t;while (t--){solve();}return 0;
}