HBC25142成绩统计,语言题,排序[USACO 2006 Ope G]The Milk Queue题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Every morning, Farmer John's N (1

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.

标签： HBC25142成绩统计 语言题 排序[USACO 2006 Ope G]The Milk Queue题解