AtCoder Beginner Contest 374 E题 Sensor Optimization Dilemma 2（二分，贪心）

题目链接

AtCoder Beginner Contest 374 E

思路

我们很容易想到直接二分答案。

因为机器$s_i$和$t_i$每天最多可以加工$100$个产品。因此，对于$s_i$和$t_i$中性价比低的那一个不会选太多。

因此我们可以直接枚举性价比低的那一台机器的数量，贪心地$check$即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, x;
int a[N], p[N], b[N], q[N];
bool check(int w)
{int cnt = 0;for (int i = 1; i <= n; i++){int res = 1e9;for (int j = 0; j <= 10000; j++){if (a[i] * q[i] > b[i] * p[i]){// b更低int op = w - j * b[i];op = max(op, 0ll);int sum = j * q[i] + (op / a[i] + (op % a[i] != 0)) * p[i];res = min(res, sum);}else{int op = w - j * a[i];op = max(op, 0ll);int sum = j * p[i] + (op / b[i] + (op % b[i] != 0)) * q[i];res = min(res, sum);}}cnt += res;}return cnt <= x;
}
void solve()
{cin >> n >> x;for (int i = 1; i <= n; i++){cin >> a[i] >> p[i] >> b[i] >> q[i];}int low = 0, high = 1e9;while (low < high){int mid = low + high + 1 >> 1;if (check(mid)){low = mid;}elsehigh = mid - 1;}cout << low << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}