P6092 [CEOI2012] 工作规划

· · 题解

题意：

有 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;//结束 
}