BZOJ 1899 [ZJOI2004]Lunch 午餐:dp+贪心

题目

题目描述

上午的训练结束了,THU ACM小组集体去吃午餐,他们一行N人来到了著名的十食堂。这里有两个打饭的窗口,每个窗口同一时刻只能给一个人打饭。由于每个人的口味(以及胃口)不同,所以他们要吃的菜各有不同,打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同,所以吃饭花费的时间也是可能有所不同的。

THU ACM小组的吃饭计划是这样的:先把所有的人分成两队,并安排好每队中各人的排列顺序,然后一号队伍到一号窗口去排队打饭,二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃,所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

现在给定了每个人的打饭时间和吃饭时间,要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

假设THU ACM小组在时刻0到达十食堂,而且食堂里面没有其他吃饭的同学(只有打饭的师傅)。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的,而且每个人打饭的时间是和窗口无关的,打完饭之后立刻就开始吃饭,中间没有延迟。

现在给定N个人各自的打饭时间和吃饭时间,要求输出最佳方案下所有人吃完饭的时刻。

输入格式

第一行一个整数N,代表总共有N个人。

以下N行,每行两个整数 Ai,Bi。依次代表第i个人的打饭时间和吃饭时间。

输出格式

一个整数T,代表所有人吃完饭的最早时刻。

说明/提示

所有输入数据均为不超过200的正整数。

题解

好像可以dp?

首先,不严谨地按照生活经验来说,如果有两个人一个吃得快一个吃得慢,那么让吃得慢的人先打饭,会让两个人都吃完的时刻提前

所以我们猜想,在任意一个窗口,都是吃的慢的先打,吃的快的后打

先给出证明如下:

假设有一最优方案 P,其中某个队列中有两个相邻的人1和2,1比2吃的快(即 b_1 < b_2),且1在2前面

则当前两个人都吃完饭的时刻为:ans_1 = max\lbrace a_1+b_1,a_1+a_2+b_2\rbrace

由于 b_1 < b_2,有 a_1+b_1 < a_1+b_2 < a_1+a_2+b_2

所以 ans_1=a_1+a_2+b_2

若将两人交换,则此时两人都吃完饭的时刻为:ans_2=max\lbrace a_2+b_2,a_1+a_2+b_1\rbrace

由于 ans_1=a_1+a_2+b_2 > a_1+a_2+b_1,且 ans_1=a_1+a_2+b_2 > a_2+b_2

所以 ans_1 > ans_2P 不为最佳方案,矛盾

所以:若有一最有方案,则队列中前面的人一定比后面的人吃得慢

所以要先把所有人按吃饭时间降序排序一下

然后开始dp

表示状态?f[i][j] 表示已经将前 i 个人分了组,第一组的人的打饭时间之和为 j,此时前 i 个人全部吃完饭所用的最少时间

如何转移?对于当前的 f[i][j] 来说,第 i 个人要么被分到了第一组,要么被分到了第二组

如果被分到了第一组,f[i][j] = max\lbrace 前i-1个人的答案,第i个人的用时\rbrace
f[i][j] = max\lbrace f[i-1][j-a[i]],j+b[i]\rbrace
同理,如果被分到了第二组:
f[i][j] = max\lbrace f[i-1][j],第i个人在第二组的用时\rbrace
i 个人在第二组的用时???不知道第二组的总排队时间啊怎么办???

如果之前我们处理一下前 i 个人的打饭时间的前缀和 s[i],那么第 i 个人在第二组的用时就是 s[i]-j+b[i]。完整转移:
f[i][j]=max\lbrace f[i-1][j],s[i]-j+b[i]\rbrace
然后统计答案呢?我们要的是所有人分完组,这样的所有状态对应答案的最小值,即:
ans=min_{j=0}^{s[n]}\lbrace f[n][j]\rbrace

Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 205
#define MAX_T 40005
#define INF 1000000000

using namespace std;

struct Data {
    int a, b;
    Data() {}
    Data(int _a, int _b) : a(_a), b(_b) {}
    friend bool operator<(const Data &x, const Data &y) {
        return x.b > y.b;
    }
};

int n, ans = INF;
int s[MAX_N];
int f[MAX_N][MAX_T];
Data t[MAX_N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &t[i].a, &t[i].b);
    }
    sort(t + 1, t + 1 + n);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + t[i].a;
    }
    memset(f, 0x3f, sizeof(f));
    f[1][0] = t[1].a + t[1].b;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= s[i]; j++) {
            if (j - t[i].a >= 0) {
                f[i][j] = max(f[i - 1][j - t[i].a], j + t[i].b);
            }
            f[i][j] = min(f[i][j], max(f[i - 1][j], s[i] - j + t[i].b));
        }
    }
    for (int j = 0; j <= s[n]; j++) {
        ans = min(ans, f[n][j]);
    }
    printf("%d\n", ans);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注