3618:Exploration

keyword

シミュレーション　C++

概要

数直線上に石が置かれていて、人が原点にいる。人は原点に近い石を拾いにいく。ある時間内に石をいくつ拾えるか求める問題。
人の動き方は完全に決まっているので、シミュレーションするだけ。

int main(){
    vector<int> plus, minus;
    int i, n, t, x, cur=0, ans=0;
    t = readint();
    n = readint();
    plus.reserve(50001);
    minus.reserve(50001);
    REP(i,n){
        x = readint();
        if(x>=0) plus.push_back(x);
        else  minus.push_back(x);
    }
    sort(ALL(plus), greater<int>());
    sort(ALL(minus));
    while(!(plus.empty() && minus.empty()) && t>=0){
        if(plus.empty()){
            t -= abs(cur-minus.back());
            cur = minus.back();
            minus.pop_back();
        }
        else if(minus.empty()){
            t -= abs(cur-plus.back());
            cur = plus.back();
            plus.pop_back();
        }
        else if(abs(minus.back()) > plus.back()){
            t -= abs(cur-plus.back());
            cur = plus.back();
            plus.pop_back();
        }
        else{
            t -= abs(cur-minus.back());
            cur = minus.back();
            minus.pop_back();
        }

        if(t < 0) break;
        ans++;
    }
    printf("%d\n",ans);
}