六年级蒟蒻来题解了!!!
题目大意:
给定你一个n,表示有n个生产线,每一个生产线都有两种机器,第i个生产线第一件产品每天可以造Ai件零件但是得付出Pi元的代价,第二件产品每天可以生产Bi件物品但是得付出Qi元的代价,然后给你x元的预算问你所有流水线中的最小值的最大值是多少?
思路:
首先我们想暴力的话肯定是不行的。所以我们只能用二分答案。那二分什么呢?我们看他这个最大值是有单调性的越大它要花的钱也就最大。我们现在就把一个选择性的问题变成了一个判断性的问题。每一次二分到的答案我们尽量的去满足他,算出它所需花的最小数然后在比较看是否符合。判断时的用暴力的思想这一道题就结束了。
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
typedef long long ll;
ll n,x;
vector<pair<pair<ll,ll>,pair<ll,ll>>>v;
ll fun(ll mid){
ll sum=0;
for(ll i=1;i<=n;i++){
ll minn=4e18;
for(int j=0;j<=v[i].sd.ft;j++){
minn=min(minn,v[i].ft.sd*j+(max(0ll,mid-j*v[i].ft.ft)+v[i].sd.ft-1)/v[i].sd.ft*v[i].sd.sd);
}
for(int j=0;j<=v[i].ft.ft;j++){
minn=min(minn,v[i].sd.sd*j+(max(0ll,mid-j*v[i].sd.ft)+v[i].ft.ft-1)/v[i].ft.ft*v[i].ft.sd);
}
sum+=minn;
if(sum>x){
break;
}
}
return sum;
}
//cout
int main(){
cin>>n>>x;
v=vector<pair<pair<ll,ll>,pair<ll,ll>>>(n+1);
for(ll i=0;i<n;i++){
cin>>v[i+1].ft.ft>>v[i+1].ft.sd>>v[i+1].sd.ft>>v[i+1].sd.sd;
}
ll l=0,r=1e9;
while(l<r){
ll mid=(r+l+1)/2;
if(fun(mid)>x){
r=mid-1;
}else{
l=mid;
}
}
cout<<r;
}