列表

详情

NC25142. [USACO 2006 Ope G]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.

输入描述

* 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.

输出描述

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

示例1

输入: 

3
2 2
7 4
3 5

输出: 

16

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 11ms, 内存消耗: 628K, 提交时间: 2023-08-15 11:22:30 

#include<bits/stdc++.h>
using namespace std;
int n, cnt, ans;
struct cow {
    int a,b;
}x[100001];

int cmp(cow o, cow p) {
    return min(o.a,p.b) < min(p.a,o.b);
}
int main() {
    scanf("%d", &n);
    for(int i=1,xx, yy;i<=n;i++)
        scanf("%d%d", &xx, &yy), x[i].a = xx, x[i].b = yy;
    sort(x+1, x+n+1, cmp);
    for(int i=1;i<=n;i++)
        cnt += x[i].a, ans = max(ans, cnt) + x[i].b;
    printf("%d", ans);
}

上一题

© 2024 nowcoder.com