abc374E Sensor Optimization Dilemma 2

abc374E 传感器优化困境 2

#include<bitsstdc++.h>
#define ll long long
#define N 105
using namespace std;
//最小值最大，二分？
//猜测最小值，每一个过程都要大于最小值，如果可行，就放大
int n;
ll ans, X;
struct Node{
	ll a,b,p,q;
}c[105];
int chk(ll w){//猜测的是产品个数（加工单位*每天每单位加工的产品个数），每一个过程需要大于等于它
	ll sum = 0;
	for(int i = 1; i <= n; i++){
		ll mn = LONG_MAX;
		for(int j = 0; j < c[i].a; j++){ //枚举加工几个单位
			mn = min(mn, j * c[i].q + (w - j * c[i].b + c[i].a - 1)/c[i].a * c[i].p);
		}
		sum += mn;
		//3 6 2 5
		//枚举性价比差的机器，加工1个单位，加工2个单位，加工3个单位，加工4个单位（是单位，不是产品）
		//枚举加工4个单位，不如3个单位性价比高的来替代，相当于枚举1个性价比差的
		//枚举加工5个单位，不如3个单位性价比高的来替代，相当于枚举2个性价比差的
	}
	return sum <= X;
}
int main(){
    cin>>n>>X;
	for(int i = 1; i <= n; i++){
		cin>>c[i].a>>c[i].p>>c[i].b>>c[i].q;
		if(c[i].a * c[i].q < c[i].b * c[i].p){
			swap(c[i].a, c[i].b);
			swap(c[i].p, c[i].q);
		}
	}
	ll l = 0, r = (int)(2e9);
	while(l <= r){
		ll mid = (l + r) >> 1;
		if(chk(mid)){
			ans = mid;
			l = mid + 1;
		}
		else	
			r = mid - 1;
	}
	cout<<ans<<endl;
	return 0;
}