川のブログ

川の適当気ままなブログです。 

AOJ 0099 Surf Smelt Fishing Contest II

こんにちかわです。

久しぶりに解いていきたいと思います。

ソースコード

#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,event;
    cin>>n>>event;
    
    vector<int> possessionfish(n+1, 0);
    vector<int>::iterator iter;
    
    int index, topNum = -1;
    int fishing,num;
    
    for(;event>0;--event){
        cin>>num>>fishing;
        possessionfish[num]+=fishing;
        
        if(topNum == -1)topNum = num;
        else if(fishing > 0){
            if(possessionfish[num] > possessionfish[topNum] || (topNum > num && possessionfish[num] == possessionfish[topNum]))topNum = num;
        }else if(topNum == num){
            iter = max_element(possessionfish.begin(), possessionfish.end());
            index = distance(possessionfish.begin(), iter);
            topNum = index;
        }
        
        cout<<topNum<<" "<<possessionfish[topNum]<<endl;
    }
}

普通に解くだけなら

iter = max_element(possessionfish.begin(), possessionfish.end());
index = distance(possessionfish.begin(), iter);
topNum = index;

の部分だけでOKですが、

計算量を減らさないといけないため

Topの人のインデックスを保存しておき、

イベントごとの釣った数が正の場合は比較、

負の場合は上記の探し出すコードを利用しました。