Lisa是一家餐厅的女服务员。今晚是它的生日，所以Lisa请求厨师长准备特别餐来招待她的朋友。厨师长的晚餐由Ｎ种烹调原料做成。为了准备晚餐上的一道菜，各种烹调原料他都需要一些。
有些烹调原料可以从厨房里得到, 剩下的烹调原料Lisa将会去杂货商店买。商店有全部所需的烹调原料，有大袋装的和小袋装的。Lisa有Ｍ美元，想用M美元让厨师长做出最多的菜。
输入
输入文件kuhar.in第一行两个整数：Ｎ、Ｍ，１≤N≤100,1≤M≤100 000。 第2…Ｎ行：每行包含６个正整数，按顺序描述每种烹调原料：
Ｘ，10≤X≤100,一道菜里需要的这种烹调原料数目；
Y，1≤Y≤100, 厨房已有这种烹调原料数目；
SM，1≤ SM<100,小袋装原料的尺寸；
PM，10≤PM<100, 小袋装原料的价格；
SV，SM<SV≤100, 大袋装原料的尺寸；
PV,PM<PV≤100, 大袋装原料的价格。
输出
输出文件kuhar.out中一个整数，表示厨师长能做出最多菜的数目。
样例输入
2 100
10 8 10 10 13 11
12 20 6 10 17 24
样例输出
5
【样例解释】
样例中，Lisa花99美元买三个小包装袋和一个大包装袋的第一种配料、一个小包装袋和两个大包装袋的第一种配料（310+111+110+224=99）。
这样的话，厨师长就会有51个（8+310+113）单位的第一种烹调原料，60个（20+16+217）单位的第二种烹调原料。
分析：刚开始看到思路很乱，觉得DP贪心都可以来一发【事实好像确实是这样的】
而我觉得二分还是挺好想到的，而研究的问题确实符合单调性，说到底，就是我有的钱，相对于我现在要买做的菜需要的材料的钱更多还是更少的问题。这样二分的模型基本抽象出来了，按这个想法只需稍加改动转化为可行与不可行就成为了check函数。而check里面一定要保证最优，所以要计算买若干食材需要的钱的最小值。数据规模并不大，枚举和背包问题都不大，这里我写了枚举。枚举k~0袋大包装，打擂台算出最小值。
呈上我Naive的代码
#include<bits/stdc++.h> using namespace std; #define N 100000000 int n,m,ans,x[110],y[110],ss[110],sp[110],bs[110],bp[110]; int l,r,mid; int check(int middle) { int money=m; for(int i=1;i<=n;i++) { int ret=N; int need=middle*x[i]-y[i]; int k=need/bs[i]; if(bs[i]*k<need)//这里是为了防止除法直接舍掉零头，所以验证了一下。有余数的情况下实际需要的应该+1； k++; while(k>=0) { int j=(max(need-bs[i]*k,0))/ss[i]; if(ss[i]*j+k*bs[i]<need)//同上理 j++; ret=min(ret,k*bp[i]+j*sp[i]); k--; } money-=ret; if(money<0)//小小地剪枝 return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d%d%d%d%d",&x[i],&y[i],&ss[i],&sp[i],&bs[i],&bp[i]); l=0;r=100000;//这里r不能太大，因为mid的大小与时间复杂度是有关的，check里k的那个循环复杂度大概是mid的百分之一，r太大的话，比较刁钻的数据就会T while(l<=r) { mid=(l+r)/2; if(check(mid)) { l=mid+1; ans=mid; } else r=mid-1; } printf("%d",ans); return 0; }