【bzoj1727】[Usaco2006 Open]The Milk Queue 挤奶队列 贪心

题目描述

Every morning, Farmer John's N (1 <= N <= 25,000) cows all line up for milking. In an effort to streamline the milking process, FJ has designed a two-stage milking process where the line of cows progresses through two barns in sequence, with milking taking part sequentially in both barns. Farmer John milks cows one by one as they go through the first barn, and his trusty sidekick Farmer Rob milks the cows (in the same order) as they are released from the first barn and enter the second barn. Unfortunately, Farmer John's insistence that the cows walk through both barns according to a single ordering leads to some inefficiencies. For example, if Farmer John takes too long to milk a particular cow, Farmer Rob might end up sitting idle with nothing to do for some time. On the other hand, if Farmer John works too fast then we might end up with a long queue of cows waiting to enter the second barn. Please help Farmer John decide on the best possible ordering of cows to use for the milking, so that the last cow finishes milking as early as possible. For each cow i we know the time A(i) required for milking in the first barn and the time B(i) required for milking in the second barn. Both A(i) and B(i) are in the range 1...20,000.

每天早晨，约翰的N(1≤N≤25000)头奶牛都排成一列，逐一挤奶．为了提高挤奶的速率，

约翰把整个挤奶过程划分成两道工序，每头牛都得连续地完成这些挤奶工序．奶牛们一个接一个地进入挤奶的牛棚，约翰负责实行第一道工序，第二道工序则让他的好友萝卜帮助完成．并且，如果某头奶牛先于另一头奶牛开始进行第一道工序，那么她开始第二道工序的时间也一定在那一头奶牛之前．    约翰发现，如果奶牛们按某种顺序排队进行挤奶，那么可能会在排队等待上多花很多的时间．比方说，如果约翰要花很长时间才能完成某头奶牛挤奶时的第一道工序，那么萝卜可能会有一段时间没有事做．当煞，如果约翰的工作完成得太快，萝}、面前就会有很多奶牛排起长队．    请你帮助约翰计算一下，如果按照最优的排队方式，最少需要多少时间才能把所有奶牛都挤过奶．对于每头奶牛，我们都知道在她身上完成第一道工序所需的时间Ai，以及完成第二道工序的时间Bi.   1≤Ai，Bi≤20000.

输入

* Line 1: A single integer, N.

* Lines 2..1+N: Line i+1 contains two space-separated integers A(i) and B(i) for cow i.

第1行一个整数N．接下来N行，每行两个整数表示第i头牛的Ai，Bi值．

输出

* Line 1: The minimum possible time it takes to milk all the cows, if we order them optimally.

输出按照最优方案排队后，最少需要多少时间才能完成对所有奶牛的挤奶．

样例输入

3
2 2
7 4
3 5

样例输出

16

提示

把奶牛们按照3，1，2的顺序排队，这样挤奶总共花费16个单位时间．

---

题解

神贪心

贪心法则：如果min(a1,b2)<min(a2,b1)，那么就先选择1再选择2，其余同理。

严格证明什么的就算了（我也不会……）就说说简单想法吧。

如果有1和2，那么先1后2的时间为a1+b2+max(b1,a2)，x先2后1的时间为a2+a1+max(b2,a1)。

要想使先1后2比先2后1合适，则应满足a1+b2+max(b1,a2)<a2+b1+max(b2,a1)。

整理得a1+b2-max(a1,b2)<b1+a2-max(b1,a2)。

两个数的和就是这两个数的最大值与最小值之和（这不是废话吗）。

于是a+b=max(a,b)+min(a,b)，即a+b-max(a,b)=min(a,b)。

由此化简上式得min(a1,b2)<min(a2,b1)。

这个条件也应该具有单调性（虽然我证不出来……）。

然后按照这个法则排序求解就行了。

#include <cstdio>

#include <algorithm>

using namespace std;

struct data

{

    int a , b;

}c[25001];

bool cmp(data x , data y)

{

    return min(x.a , y.b) < min(x.b , y.a);

}

int main()

{

    int n , i , w = 0 , ans = 0;

    scanf("%d" , &n);

    for(i = 1 ; i <= n ; i ++ )

        scanf("%d%d" , &c[i].a , &c[i].b);

    sort(c + 1 , c + n + 1 , cmp);

    for(i = 1 ; i <= n ; i ++ )

    {

        ans += c[i].a;

        w = max(c[i].b , w - c[i].a + c[i].b);

    }

    printf("%d\n" , ans + w);

    return 0;

}