BZOJ1727：[Usaco2006 Open]The Milk Queue挤奶队列

我对\(Jhonson\)算法的理解：https://www.cnblogs.com/AKMer/p/9863620.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1727

\(Jhonson\)算法裸题，题目还告诉你如果某头奶牛先于另一头奶牛开始进行第一道工序，那么她开始第二道工序的时间也一定在那一头奶牛之前，可谓非常良心了。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=25005;

int n,ans;

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct cow {
    int a,b;

    bool operator<(const cow &tmp)const {
        return min(a,tmp.b)<min(tmp.a,b);//如果写<=的话莫名ＲＥ，求大佬指教。写成<也不影响正确性
    }
}p[maxn];

int main() {
    n=read();
    for(int i=1;i<=n;i++)
        p[i].a=read(),p[i].b=read();
    sort(p+1,p+n+1);int T=0;
    for(int i=1;i<=n;i++) {
        ans+=p[i].a;
        T=p[i].b+max(T-p[i].a,0);//排完序直接模拟就可以了
    }
    printf("%d\n",ans+T);
    return 0;
}

BZOJ1727：[Usaco2006 Open]The Milk Queue挤奶队列

原文：https://www.cnblogs.com/AKMer/p/9864527.html