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の人のインデックスを保存しておき、
イベントごとの釣った数が正の場合は比較、
負の場合は上記の探し出すコードを利用しました。