USACO12JAN爬山

发表于
  • Description
    $N (1\le N\le 25000)$头奶牛，第$i$头奶牛上山耗时$U_i$，下山耗时$D_i$。同一时刻最多只能有一头奶牛，下山也是。上山下山顺序可以不一样，求最后一头奶牛到达的最早时间。
  • Solution
    假设上山总时间大于下山总时间，那么最后会有一只奶牛在山上，让这只奶牛下山时间最小即可。
    否则，使最开始上山那只奶牛上山时间最少即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    #include <bits/stdc++.h>
    using namespace std ;
    void Read ( int &x, char c = getchar() ) {
        for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
        for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    }
    const int zhf = 1<<29 ;
    int n, m ;
    int main() {
    #ifndef ONLINE_JUDGE
        freopen ( "P1561.in", "r", stdin ) ;
        freopen ( "P1561.out", "w", stdout ) ;
    #endif
        int i, st, end, up, down, x ;
        Read(n) ;
        st = end = 0 ;
        up = down = zhf ;
        for ( i = 1 ; i <= n ; i ++ ) {
            Read(x) ;
            st += x ;
            up = min(up, x) ;
            Read(x) ;
            end += x ;
            down = min(down, x) ;
        }
        printf ( "%d\n", max(st+down, end+up) ) ;
        return 0 ;
    }