うーん、タグで解法バレバレだな…。
http://yukicoder.me/problems/28
問題
自分と相手はN匹のモンスターを持っており、それぞれのレベルA[i]、B[i]が与えられる。
敵のモンスターは円状に並んでおり、最初の1匹B[i]を任意に選択すると、以後B[i+1]、B[i+2]…と順に戦っていく。
自分がモンスターを出す順番は決まっており、
- 手持ちで一番レベルが低いモンスター
- 最低レベルのモンスターが複数いるなら、戦闘回数が最小のものを選択
両者のモンスターのレベルにかかわらず自分のモンスターは必ず勝利し、その際敵モンスターのレベルの半分の自分のレベルに加算する。
N匹の戦闘を終えた後、自分の最多戦闘回数のモンスターの戦闘回数が最小となるよう、最初の1匹を選択し、最多戦闘回数を答えよ。
解法
愚直にB[0]~B[N-1]それぞれを先頭とするパターンを総当たりすればよい。
自分のモンスターは(レベル*100000+戦闘回数)でpriority_queueでソートすれば、常に次に戦うモンスターをpopできる。
よって全体で計算量はO(N^2*logN)かな。
int N; int A[2000],B[2000],L[2000]; int num[2000]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; FOR(i,N) cin>>B[i]; int mi=10000; FOR(i,N) { ZERO(num); priority_queue<pair<int,int> > P; FOR(x,N) L[x]=A[x]; FOR(x,N) P.push(make_pair(-L[x]*100000,x)); FOR(x,N) { pair<int,int> p=P.top(); P.pop(); num[p.second]++; L[p.second] += B[(i+x)%N]/2; P.push(make_pair(-L[p.second]*100000-num[p.second],p.second)); } mi=min(mi,*max_element(num,num+N)); } cout<<mi<<endl; }
まとめ
☆3つはDiv2 Medium位かな?Div1 Easyより少し簡単な気がする。