自动搬运

查看原文

来自洛谷，原作者为

	OI_StarGod 盼君勿忘 || infj-t || 学术&关私信了

搬运于2025-08-24 22:17:19，当前版本为作者最后更新于2023-11-06 13:36:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

有 $m$ 个食物在 $n$ 天内生产出来，保质期为 $d$ 天，需要有人吃掉这些食品，每个人每天只能吃一个食品，求至少需要几个人能吃光食品并且食品不过期。

暴力解法：

大家注意，考场上，优先暴力，除非正解非常简单。

那这道题暴力怎么解呢？首先，我们可以发现，用 $m$ 个人吃最简单，没人吃一个即可。因此，我们枚举 $1$ 到 $m$ 间的每个数，判断能不能，找到就输出。

判断方法：

我们可以轻松发现，先吃早的食品一定比先吃晚的食品完成更好。因为早的食品保质期更早，所以先按时间排一下序。接下来，只要模拟一下就行了。

判断代码：

bool check(int x) {//判断函数
	int sum = 0;//记录当前完成了几个任务。
	for (int i = 1; i <= n; ++i) {//当前是第几天
		if (sum >= m) {//如果完成的任务数和总任务数相同
			return 1;//已经完成了任务，x个人是可行的，返回true
		}
		for (int j = 1; j <= x; ++j) {//枚举每台机器
			if (a[sum] <= i && sum < m) {//如果这个食品已经生产出来了并且食品还没有吃完
				if (a[sum] + d < i) {//如果这个食品过期了，说明会吃不完
					return 0;//x个人不可行
				}
				++sum;//否则，吃掉这个食品
			}else {//如果食品还没生产出来或者已经生产完了
				break;//今天无法完成更多食品了，跳到下一天
			}
		}
	}
	return sum >= n;//返回是否吃完了食品
}

暴力代码：

#include <bits/stdc++.h>
using namespace std;
int n, d, m;
int a[1000005];
int sum;
bool check(int x) {//判断函数
	sum = 0;//记录当前完成了几个任务。
	for (int i = 1; i <= n; ++i) {//当前是第几天
		if (sum >= m) {//如果完成的任务数和总任务数相同
			return 1;//已经完成了任务，x个人是可行的，返回true
		}
		for (int j = 1; j <= x; ++j) {//枚举每台机器
			if (a[sum] <= i && sum < m) {//如果这个食品已经生产出来了并且食品还没有吃完
				if (a[sum] + d < i) {//如果这个食品过期了，说明会吃不完
					return 0;//x个人不可行
				}
				++sum;//否则，吃掉这个食品
			}else {//如果食品还没生产出来或者已经生产完了
				break;//今天无法完成更多食品了，跳到下一天
			}
		}
	}
	return sum >= n;//返回是否吃完了食品
}
int main() {//主函数
	scanf("%d%d%d", &n, &d, &m);//输入
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &a[i]);//存食品的生产日期
	}
	sort(a + 1, a + m + 1);//按生产日期从小到大排序
	for (int i = 0; i <= m; ++i) {//循环枚举有几个人
		if (check(i)) {//如果可以
			printf("%d", i);//输出
			break;//跳出
		}
	}
	return 0;//结束
}

期望得分：50 分。

实际得分：65 分。

提交记录

PS：为什么前面的点 TLE 了，后面的反而 AC 了？

正解：

我们想一想，时间在枚举上花了很多，这要怎么优化呢？

方法当然是有的：

二分：

翻了一遍题解，没有人讲到二分到底是什么，这对蒟蒻很不友好。所以我来科普一下：

比如我们是在一个升序数组中查找元素。

朴素方法：遍历一遍整个数组。

高级方法：它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。——oi-wiki

简单来说就是每次查找中间元素，由于数组有序，所以如果没找到就可以将区间缩小一半，就这样不断缩小，最后当区间大小缩小到 1 时就可以确定答案。

如何运用到这道题呢？

我们想想，二分要求什么？

单调性 有序！

这题有序吗？我们看，$x$ 个人能吃掉的，$(x+1)$ 个人也一定能吃掉，所以可以二分。

你们最爱的代码来了。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
int n, d, m;
int a[1000005];
int l = 0, r, mid;
int sum;
bool check(int x) {//判断函数
	sum = 0;//记录当前完成了几个任务。
	for (int i = 1; i <= n; ++i) {//当前是第几天
		if (sum >= m) {//如果完成的任务数和总任务数相同
			return 1;//已经完成了任务，x个人是可行的，返回true
		}
		for (int j = 1; j <= x; ++j) {//枚举每台机器
			if (a[sum] <= i && sum < m) {//如果这个食品已经生产出来了并且食品还没有吃完
				if (a[sum] + d < i) {//如果这个食品过期了，说明会吃不完
					return 0;//x个人不可行
				}
				++sum;//否则，吃掉这个食品
			}else {//如果食品还没生产出来或者已经生产完了
				break;//今天无法完成更多食品了，跳到下一天
			}
		}
	}
	return sum >= n;//返回是否吃完了食品
}
int main() {
	scanf("%d%d%d", &n, &d, &m);//输入 
	r = m;//设置最大值 
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + m + 1);//排序 
	while (l < r) {//二分 
		mid = (l + r) >> 1;//取中间值 
		if (check(mid)) {//如果可以 
			r = mid;//看看有没有更少的人 
		}else {
			l = mid + 1;//看看有没有更多得人 
		}
	}
	printf("%d", r);//输出 
	return 0;//结束 
}