难度：提高+/省选-

题目描述

        上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。
        THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

        现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
        假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。
        现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

Sample input

5
2 2
7 7
1 3
6 4
8 5

Sample output

17

说明

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

题解

        考察动态规划和贪心。
        首先应明确：在所有人都在一个队列中时，按照每个人吃饭时间降序排列才可以获得最优解。这是一种贪心思想，是比较容易发现的，下面给出它的数学证明：
        考虑两个相邻的人，假设他们前面的人总共打饭时间为p，那么如果第一个人在前，他们两人的吃完饭最晚时刻为

        反之为

        假设第一个在前更优，则有

        注意到$p+a1+b1<p+a1+a2+b1$并且$p+a2+b2<p+a1+a2+b2$，因此上式等价于

        也就是$b1≥b2$，即吃饭时间长的在前更优。根据相邻全局最优化原理（还记得皇后游戏吗？）可知按照吃饭时间降序排列的贪心策略是正确的。证毕。
        于是先对这些数据按照第二元素（也就是吃饭用时）降序排列，那么问题的重点就是如何对他们进行分队安排，这是一个动态规划。
        由于每一个人都有进入两个队列任意一个的决策，于是考虑决策转移。记dp(i，j，k)表示到第i个人，在第一个队列已用时j单位时间，第二个队列已用时k个单位时间的情况下，能得到的最早的吃饭完成时刻。这里的j、k已经包含了i这个人本身的打饭时间。那么有状态转移方程：

        方程比较容易理解，两个状态分别表示将第i个人分配到第一个队列和第两个队列。如果无法分配，则直接分配到另一个合法的队列。
        但是注意到这样开三维数组很容易MLE，又发现j+k=sum(i)恒成立，这也就是说j和k本身就有关系，在这个情况下j和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
#include<iostream>
#include<algorithm>

#define N 200
#define inf (int)1e8
using namespace std;
int n, dp[N][N * N + 1];
int sum[N] = {0};

struct node {
    int a, b;

    bool operator<(node x) { return b > x.b; }
} op[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)cin >> op[i].a >> op[i].b;
    sort(op, op + n);
    sum[0] = op[0].a;
    for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + op[i].a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= sum[n - 1]; j++)dp[i][j] = inf;
    }
            dp[0][0] = dp[0][op[0].a] = op[0].a + op[0].b;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= sum[i]; j++) {
            if (j >= op[i].a)dp[i][j] = min(dp[i][j], max(dp[i - 1][j - op[i].a], j + op[i].b));
            if (sum[i] - j >= op[i].a)dp[i][j] = min(dp[i][j], max(dp[i - 1][j], sum[i] - j + op[i].b));
        }
    }
    int ans = inf;
    for (int i = 0; i <= sum[n - 1]; i++)ans = min(ans, dp[n - 1][i]);
    cout << ans;
    return 0;
}

        进一步观察可发现，状态转移方程的量仅限于相邻两行之间，于是可以把数组压缩至一维，这也是本题目前最好的解法。
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
#include<iostream>
#include<algorithm>

#define N 200
#define inf (int)1e8
using namespace std;
int n, dp[N * N];
int sum[N] = {0};

struct node {
    int a, b;

    bool operator<(node x) { return b > x.b; }
} op[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)cin >> op[i].a >> op[i].b;
    sort(op, op + n);
    sum[0] = op[0].a;
    for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + op[i].a;
    for (int j = 0; j <= sum[n - 1]; j++)dp[j] = inf;
    dp[0] = dp[op[0].a] = op[0].a + op[0].b;
    for (int i = 1; i < n; i++) {
        for (int j = sum[i]; j >= 0; j--) {
            int p = inf;
            if (j >= op[i].a)p = min(p, max(dp[j - op[i].a], j + op[i].b));
            if (sum[i] - j >= op[i].a)p = min(p, max(dp[j], sum[i] - j + op[i].b));
            dp[j] = p;
        }
    }
    int ans = inf;
    for (int i = 0; i <= sum[n - 1]; i++)ans = min(ans, dp[i]);
    cout << ans;
    return 0;
}