题解 - P6243

· · 题解

P6243 The Milk Queue G（挤奶序列 G） の 题目传送门。

题目简化

给定两个序列 a, b。
对于每个 a_i, b_i，需先花费 a_i 的时间，再花费 b_i 的时间，在完成 b_i 时，可以同时完成 a_{i+1}。

请排出花费最小时间的序列并求最小时间。

思路讲解

这题是很明显的贪心，因为他让你排序，一般 dp 的题是不会让你乱搞的。
那么知道了贪心，就要知道贪心策略。

设为 牛 x 与 牛 y 排序。

先提出结论：

\min(a_x, b_y) < min(a_y, b_x)

证明

首先可以得出 牛 x 在 牛 y 前面所用的时间：

a_x + b_y + \max(a_y, b_x)

就是（牛 x 的第一道工序）加上（牛 x 的第二道工序与 牛 y 的第一道工序的较长时间）（因为经过那段时间 Rob 才能给 牛 y 做第二道工序）加上（牛 y 的第二道工序）

同理，可以得出 牛 y 在 牛 x 前面所用的时间：

a_y + b_x + \max(b_y, a_x)

要最短时间，就要先做时间短的，得：

a_x+b_y+\max(a_y, b_x) < a_y+b_x+\max(b_y, a_x)

化简得：

\min(a_x, b_y) < \min(b_x, a_y)

Q.E.D.

讲一下如何化简的（我自己在这里就懵了：

a_x+b_y+\max(a_y, b_x) < a_y+b_x+\max(b_y, a_x) \max(a_y, b_x)-a_y-b_x < \max(b_y, a_x)-a_x-b_y -\min(a_y, b_x) < -\min(b_y, a_x) \min(a_x, b_y) < \min(b_x, a_y)

代码实现

如果光用贪心排序的话，后方无法及时更新，每次都向前算一遍稳稳 T 飞。

使用前缀和。

CODE：

#include <bits/stdc++.h>
using namespace std;
const int man = 25e3+10;
struct cow { int a, b;} c[man];

int n, sum, res;
bool cmp (cow x, cow y) { return min(x.a, y.b) < min(x.b, y.a);}
int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &c[i].a, &c[i].b);
    sort(c+1, c+n+1, cmp);//按 cmp 排序
    for (int i = 1; i <= n; ++ i) {
        sum += c[i].a;//前缀和
        res = max(res, sum)+c[i].b;
    }
    printf("%d", res);
    return 0;
}

E.N.D.