abc 374 E (二分答案贪心)
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 的效益,判断花销是否超过x
auto 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;
else
r = 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;
}
原文地址:https://blog.csdn.net/x1653673086/article/details/142744512
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!