kuangbin 专题二十三：二分 尺取 单调栈队列 Inviting Friends

队列 Inviting Friends"/>

kuangbin 专题二十三：二分 尺取 单调栈队列 Inviting Friends

题目链接：
传送门

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N = 800000;
const int M = 110;
int ans, n, m, x[M], y[M], s[M][3], p[M][3], dp[N];//完全背包
int pack(int k, int dif) {//初始化体积和最小值int v = dif + s[k][2], mn = INF;//初始化dpfor(int i = 1;i <= v; i++) dp[i] = INF;dp[0] = 0;//完全背包求拿够差值的情况下最少的花费for(int i = 1; i <= 2; i++) {for(int j = s[k][i]; j <= v; j++) {dp[j] = min(dp[j], dp[j - s[k][i]] + p[k][i]);}}//找出大于等于所需中的最小值for(int i = dif; i <= v; i++) mn = min(mn, dp[i]);return mn;
}//判断当前人数是否符合条件
bool check(int num) {//初始化花费int cost = 0;//判断每种情况下缺少的材料的最小花费之和是否在预定金额内for(int i = 1; i <= n; i++) {//算出还差多少材料int dif = num * x[i] - y[i];//如果材料有欠缺，则用完全背包算出当前情况下需要多少if(dif > 0) {cost += pack(i, dif);if(cost > m) return 0;}}return 1;
}int main() {while(scanf("%d%d", &n, &m) != EOF) {if(n == 0 && m == 0) break;//初始化左指针和右指针int l = 0, r = INF;for(int i = 1; i <= n; i++) {scanf("%d%d%d%d%d%d", &x[i], &y[i], &s[i][1], &p[i][1], &s[i][2], &p[i][2]);//这里先进行一个预处理求出r的最大范围，不然很容易超时if(s[i][1]*1.0 / p[i][1] >= s[i][2]*1.0 / p[i][2]) {r = min(r, ((m / p[i][1] * s[i][1]) + y[i]) / x[i]);}else {r = min(r, ((m / p[i][2] * s[i][2]) + y[i]) / x[i]);}}//二分最大人数while(l < r) {int mid = l + r >> 1;if(check(mid)) ans = mid, l = mid + 1;else r = mid;}//输出printf("%d\n", ans);}return 0;
}

这是一道二分+完全背包的题
首先讲讲这道题的大概意思，我们可以这么理解，我们有n种材料
每种材料有6个参数：
x代表制作一份食物需要消耗多少份当前材料
y代表当前已拥有多少份这种材料
s1代表购买大包装食材，每份包装中含有多少份当前材料
p1代表购买大包装食材，每份需要花费多少钱
s1代表购买小包装食材，每份包装中含有多少份当前材料
p1代表购买小包装食材，每份需要花费多少钱
最后还有一个m代表当前手中拥有的钱数

明确题意后我们可以开始做题了
首先问题是我们能最多服侍多少个人，那么我们就二分查找最多能服侍多少个人。
接下来我们来分析一下我们要如何确定二分条件呢？首先我们可以通过价钱来进行判断，当前的人数是否符合要求。具体做法是：枚举每一种食材在当前的人数下的需求量（差多少），然后求出不足这些缺少食材所需的花费，如果所有食材购买足量所需的花费大于我们持有的钱数，那么就说明不符合要求，要往下找，否则就是符合要求，可以往上找。
接下来就要处理什么我们要如何计算补足当前材料的最小花费，这个时候就要使用完全背包。完全背包在枚举时，背包就是大包装和小包装，容量就是差值 + 大包装的份量，加上大包装的份量主要是因为在做背包问题时，我们并不需要把整个背包完全装满。但是在这道题中，我们不足的差额是一定要补完的，所以我们要在加一个大包装的份量，然后在所需数量到差值 + 大包装的份量这个区间内取最小值。以此来获取最小花费。
完成上面的步骤就基本做完了，但是还有一个坑点，就是极容易超时，因此我们在输入数据时，可以对数据进行预处理，以此来确定r的最大可能。每次输入时，我们判断假设其他材料都很充足，所有钱都花在当前材料上的情况下，能最多服侍多少个人，枚举所有情况然后取最小值（取最小值是因为短板效应）这个值就是能取到的最大值。