3672:Long Distance Racing

keyword

Greedy　C

概要

少女はM(<10^7)秒間走る。前方にはT(<10^5)個の上り坂と平地と下り坂がある。少女はM秒のうちに出発点まで戻らなければならない。上り坂、平地、下り坂を走るのにそれぞれU,F,D秒かかる。少女はどこまで遠くにいけるか求める問題。家に帰るときは上りと下りが逆転することに気をつけること。
左から順に帰るときのコストも含めて距離を伸ばしていく。つまり上りと下りに区別はない。計算量O(T)。

int M, T, U, F, D;
char way[100009];

int solve(){
    int i, time=0;
    for(i=0;i<T;i++){
        time += way[i] == 'f' ? 2*F : U+D;
        if(time  > M)
            return i;
    }
    return T;
}