遅くなりましたが
遅くなりましたが、SRM573 div2 level2の問題を解きました。
TopCoder Statistics - Problem Statement
問題:3人チームを組んで大会に出たよ。3*N人の強さがベクトルで与えられる。
最初の三つが自分のチーム。チーム力は全員の合計値から最弱の人の力を引いたもの、
つまり強い二人の合計値。最悪の可能性を考えると、自分たちのチームは何位になるかな。
解き方。まず、最強の人を選ぶ。そのあと、二人の合計が自チームのチーム力を上回り、その中で最弱の野郎を選ぶ。
これを繰り返す。
#include <iostream> #include <sstream> #include <string> #include <vector> using namespace std; class TeamContestEasy{ public: int worstRank(vector <int> a){ int myS,rank=1,k=0,j,l,v=a.size()-3; vector <int> b; sort(a.begin()+3,a.end()); myS=a[0]+a[1]+a[2]-min(a[0],min(a[1],a[2])); cout << myS <<endl; cout << a[0] <<" "<<a[1]<<" "<<a[2]<<endl; for(int i=3;i<a.size();i++){ b.push_back(a[i]); cout << b[i-3] <<" "; } cout <<endl; for(l=v-1;l>0;l--){ for(j=k;j<v;j++){ if(myS < b[l]+b[j]){ rank++;k=j+1;break; } } if(j+1 >= l){cout <<rank<<endl; return rank;} } cout <<rank<<endl; return rank; } };
- sortで昇順に並ぶ。
- 右はlで、左はjで数える。
- lとjがぶつかったら終わり。