洛谷2577 午餐

Posted on | Edited on | In | Comments:
题解

题目

题目描述

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

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

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

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

1
2
3
4
5
6
5
2 2
7 7
1 3
6 4
8 5

输出样例#1：

1
17

题解

吃饭时间越长越早排队

  • 假设有一个最优分组方法，其中第一队内是按吃饭时间长短排序的——越长排在越前。然后尝试交换该队内的某两个人，i、j ——即原先是i 排在j 前面，并且两人各自的吃饭时间$b[j]<b[i]$，现在交换过来
  • 首先，交换前从队头到到j 总的打饭时间或者是交换后从队头到i 的总的打饭时间都是$T$
  • 然后以前$T$时间后，j 开始吃饭，现在是$T$时间后，i 开始吃饭。如果以前最终吃饭完成的时间是$T+b[j]$ （$b[j]$ 是j 的吃饭时间），那么现在就是$T+b[i]>T+b[j]$ 。如果以前最终吃饭完成时间比$T+b[j]$ 后，那么现在最终吃饭完成时间就大于或者等于$T+b[i]$

如何记录状态以及状态转移方程

  • $dp[i][j][k]$ ：表示当排到第i 个人时，第一队的排队耗时是j ，第二队的排队耗时是k

  • 先定义符号，$man[i].a$ 表示第i 人的打饭时间，$man[i].b$ 是第i 人的吃饭时间，$sum[x]=\Sigma_{i=0}^x man[i].a$

  • 因为，对于确定的i ，$k=sum[i]-j$ ，所以，$dp[i][j][k]=dp[i][j][sum[i]-j]$ 

  • 1
    2
    3
    int x = MAX(dp[i-1][j-man[i].a][k], j+man[i].b);
    int y = MAX(dp[i-1][j][k-man[i].a], k+man[i].b);
    dp[i][j][k] = dp[i][j][sum[i]-j] = MIN(x, y);

  • 之所以要取MAX，是因为$dp[i-1][j-man[i].a][k]$ 可能是第一队达到的最长吃饭完成时间，也可能是第二队达到的，而即使是第一队达到的，也有可能现在第一队最后一个吃完的时间$j+man[i].b$ 比$dp[i-1][j-man[i].a][k]$ 早，所以要取MAX

  • 因为无需枚举k ，所以无需使用三维数组。并且可以使用滚动数组，从而压缩为一维数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#define FWD(x, b, e) for (int x = b; x < e; x++)
#define BWD(x, b, e) for (int x = b; x >= e; x--)
#define INF 0x3f3f3f3f
using namespace std;

inline int MAX(int x, int y) { return x < y ? y : x; }

inline int MIN(int x, int y) { return x < y ? x : y; }

struct Node {
    int a, b;// a is pick time, b is eat time
    bool operator<(const Node &y) const { return this->b > y.b; }
};
Node man[300];
int dp[80010];
int sum[300];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &man[i].a, &man[i].b);
    }
    sort(man, man + n);

    sum[0] = man[0].a;
    FWD(i, 1, n) { sum[i] = sum[i - 1] + man[i].a; }
    memset(dp, 10, sizeof(dp));
    dp[0] = man[0].b + man[0].a;
    dp[man[0].a] = man[0].b + man[0].a;
    FWD(i, 1, n) {
        BWD(j, sum[i], 0) {
            int tmp1 = INF, tmp2 = INF;
            if (j >= man[i].a) {
                tmp1 = MAX(dp[j - man[i].a], j + man[i].b);// 第一个人放在1队
            }
            if (sum[i] - j >= man[i].a) {
                tmp2 = MAX(dp[j], sum[i] - j + man[i].b);// 第i个人放在二队
            }
            // 如果j只能允许man[i].a放在一队，则i就放一队
            if (j >= man[i].a && sum[i] - j < man[i].a) {
                dp[j] = tmp1;
            }else if (j < man[i].a && sum[i] - j >= man[i].a) {
                dp[j] = tmp2;
            }else if (j >= man[i].a && sum[i] - j >= man[i].a) {
                dp[j] = MIN(tmp2, tmp1);
            }
        }
    }
    int ans = INF;
    FWD(i, 0, sum[n - 1] + 1) { ans = ans < dp[i] ? ans : dp[i]; }
    printf("%d\n", ans);
}

  • 注意，在枚举$dp[i][j]$ 的j 时，要注意该j 是否允许man[i].a 放在第一队，或者会放在第二队，所以，给$dp[i][j]$ 赋值时也要注意是否只能放在其中一队，从而直接赋值就行了，如果能放在其中两队，那么就要取MIN

  • 注意，此题初始化时不可以把从$man[i].a+1$ 到$sum[n-1]$ 的dp都赋值为$man[i].a+man[i].b$ ，而应该赋值为INF。因为后面进行dp时，枚举$j$ 时，可能出现一种情况$j<man[i].a$ 导致这个j时不可以放在第一队，并且$sum[i]-j<man[i].a$ 导致也不可以放在第二队，这种情况就应该INF。

  • 此题如果使用自顶向下应该可以节省一些冗余状态——就是直接把上面的循环改成尾递归

  • 截图来源