読者です 読者をやめる 読者になる 読者になる

マトリョーシカ的日常

ワクワクばらまく明日のブログ。

キルア的相手チーム考察(SRM573 div2 level2)

遅くなりましたが

http://instagr.am/p/XE11eSBBAR/

遅くなりましたが、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がぶつかったら終わり。