P6243 [USACO06OPEN] The Milk Queue G-题解

skyx · 2025-07-23 16:42:36 · 题解

P6243 [USACO06OPEN] The Milk Queue G-题解

简要题意

每头奶牛需要进行两道工序，FJ 完成第一道（耗时 a_i），Rob 完成第二道（耗时 b_i）。工序必须按顺序进行，且不能交叉执行。

决定奶牛的排队顺序，使得所有奶牛的工序完成的全程时间最短。

题目分析

考虑两头牛？

对于一类重点考虑选择顺序的问题，我们可以假设 A 在 B 前面比 B 在 A 前面更优，并分析关系。这种方法一般称作 exchange argument。

我们先考虑两个奶牛的情况：奶牛 1 为 (a_1, b_1)，奶牛 2 为 (a_2, b_2)。

若先安排奶牛 1，再安排奶牛 2，所需时间为： T_{1\rightarrow2} = a_1 + \max(b_1, a_2) + b_2
若顺序调换，先 2 后 1： T_{2\rightarrow1} = a_2 + \max(b_2, a_1) + b_1
我们希望选择更小的那个时间。

对两个表达式做展开比较：

这里有 \max(x,y)=x+y-\min(x, y) ，在两个数中减去较小的，剩下较大的。

T_{1\rightarrow2} = a_1 + b_1 + a_2 + b_2 - \min(b_1, a_2)

T_{2\rightarrow1} = a_1 + b_1 + a_2 + b_2 - \min(b_2, a_1)

若希望 T_{1\rightarrow2}<T_{2\rightarrow1}，则需：

\min(b_1, a_2) > \min(b_2, a_1)

但是，这真的对吗？

我们尝试这两组数据：

排列后的最终结果分别为：

排序方式不同，得到的答案也不同。

经过验证，我们发现这两种方式都符合 \min(b_1, a_2) > \min(b_2, a_1)，排序完成后任意交换相邻元素能使答案更优，那这个排序关系就是错误的。那为什么会这样呢？

先了解几个概念：

传递性是数学中描述二元关系的一个核心特性。它指的是：若在某集合 X 上，元素 a 与 b 存在某种关系，且 b 与 c 也存在该关系，则 a 与 c 之间也必须存在这种关系。

小于关系是传递的，因为如果 a < b 且 b < c，那么 a < c。

有集合 X 和一个二元关系 R，如果它们之间没有确定的顺序或优劣关系，我们就说 a, b \in X 是不可比的。

在集合的子集包含关系 \subseteq 中，\{1\} 和 \{2\} 是不可比的，因为：
\{1\} \nsubseteq \{2\},\quad \{2\}\nsubseteq \{1\}.

我们可以通过上面的尝试发现，结果不同的主要原因是 sort 函数无法正确排序。我们知道，C++ 标准库要求用于排序的运算符必须满足严格弱序。

对于一个比较运算符，若满足以下四个条件，则称其是满足严格弱序的：

非自反性

非对称性

传递性

不可比性的传递性

在相关解答中已经证明，\min(b_1, a_2) > \min(b_2, a_1) 是传递的，我们聚焦于于不可比性的传递性：

考虑这三个元素：

A = (5, 8)
B = (2, 2)
C = (4, 7)

比较两个元素，看
\min(b_x, a_y) \quad \text{和} \quad \min(b_y, a_x)
谁大，谁小，是否相等。
如果相等则不可比，否则可比，并以较小的那一方为“较小”的元素。

对 A = (5, 8),B = (2, 2)，有：

\min(b_A, a_B) = \min(8, 2) = 2

\min(b_B, a_A) = \min(2, 5) = 2

结果相等，不可比。

对 B = (2, 2),C = (4, 7), 有：

\min(b_B, a_C) = \min(2, 4) = 2

\min(b_C, a_B) = \min(7, 2) = 2

结果相等，不可比。

对 A = (5, 8),C = (4, 7)，有：

\min(b_A, a_C) = \min(8, 4) = 4

\min(b_C, a_A) = \min(7, 5) = 5

4 < 5 \Rightarrow A < C

则 A 和 C 可比。

这个例子清楚地说明：即使两个元素分别与第三个元素都不可比，它们之间也可能是可比的。因此，该关系的不可比性不具备传递性。

所以，通过 \min(b_1, a_2) > \min(b_2, a_1) 这样的排序关系有失严谨。

考虑总时间？

考虑这三个例子：

灰色是没有牛在当前工序的时间。

结合题意，我们能贪心地得出以下结论：

第一条工序不会停止，因为我们想让总时间最少的话，就应当让第一道工序源源不断加工产品，所以决定答案的是第二道工序的开始时间（也就是第一个任务在第一道工序的时间），以及停滞时间。
最坏的情况是什么呢？

一个产品的 b_i 很小，下一个产品的 a_{i+1} 很大。
所以，前一个产品完成时，下一个产品的第一道工序还没完成，就会导致第二道工序有停滞时间。
最好的情况是什么呢？

一个产品的 a_i 很小，但是 b_i 很大。
这样会有越来越多的产品在完成第一道工序后，等待第二道工序开始，不会造成第二道工序停工等待，从而提高效率。

综上，我们得到了排序的优先级：

若 a_i < b_i，是第一优先级；
若 a_i = b_i，是第二优先级；
若 a_i > b_i，是第三优先级。

那对于每一个优先级内部，我们又要如何处理呢？

再回顾一下!

考虑图中的第一、第二种方案，对第一优先级，我们要最小化第二道工序的开始时间，也就是最小化第一个任务在第一道工序的时间。

对于同优先级的其他任务，可以推广这个结论，让第一道工序尽快处理掉容易的任务，从而让第二道工序更早开始，避免等待。

对第二优先级，优先处理 a_i 小的任务也能让流水线更快地“铺开”，避免前期积压。

而对于第三优先级，把 b_i 小的任务排前面，会导致第二道工序很快就干完了，然后等前面的任务还没处理完，造成浪费，所以应推迟那些容易处理完的任务进入第二工序，避免在中间或最后浪费时间。

所以，我们完善了以下排序规则：

若 a_i < b_i，是第一优先级，按照 a_i 从小到大排序；
若 a_i = b_i，是第二优先级，按照 a_i 从小到大排序；
若 a_i > b_i，是第三优先级，按照 b_i 从大到小排序。

实际上，对于 a_i = b_i 的情况，存在多种排序策略均是可以的。
代码实现

#include <bits/stdc++.h>
using namespace std;
struct wu
{
    int a,b,id,lei;
} p[2000005];
bool cmp(wu q,wu w)
{

    if(q.lei!=w.lei)
    {
        return q.lei>w.lei;
    }
    else
    {
        if(q.lei>=0)
        {
            return q.a<w.a;
        }
        else return q.b>w.b;
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i].a;
        cin>>p[i].b;
        p[i].id=i;
    }
    for(int i=1; i<=n; i++)
    {

        if(p[i].a<p[i].b) p[i].lei=1;
        if(p[i].a==p[i].b) p[i].lei=0;
        if(p[i].a>p[i].b) p[i].lei=-1;
    }
    sort(p+1,p+n+1,cmp);
    int ta=0;
    int tb=0;
    for(int i=1; i<=n; i++)
    {
        ta+=p[i].a;
        tb=max(ta,tb)+p[i].b;
    }
    cout<<tb<<endl;

    return 0;
}

P6243 [USACO06OPEN] The Milk Queue G-题解

P6243 [USACO06OPEN] The Milk Queue G-题解

简要题意

题目分析

考虑两头牛？

考虑总时间？

代码实现