Yukicoder009 モンスターのレベル上げ

問題概要

$N$匹のモンスターを持っており、敵のモンスターも$N$匹いる。戦わせたとき必ず勝利でき、初期レベルの$a[i]$から戦闘をした敵のレベル$b[j]$の半分だけレベルが上がる。 戦闘を行う際、$b$ははじめのモンスターを決定すると順番が決定する。自分はレベルが低く、最も戦闘を行っていないモンスターを戦わせる。 このようにして戦闘を行うとき、自分が手持ちのモンスターで戦闘回数が最も多いものを最小化する。このときの戦闘回数が最も多い数は。

$N\leqq1.5*10^3$、$a[i]\leqq10^4$、$b[i]\leqq10^4$

yukicoder009

解法

愚直$b[i]$の先頭を全探索する。 ただし自分の手持ちのモンスターを選ぶのを毎回やるとダメなので適当なヒープを持ってくる。(C++には二分ヒープなどが標準ライブラリにある。) yukicoderははやい。

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    using VL = vector<LL>;        using VVL = vector<VL>;
    
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VL a(N), b(N);
        FOR(i, 0, N) {
            cin >> a[i];
        }
        FOR(i, 0, N) {
            cin >> b[i];
        }
        ans = INF;
        FOR(s, 0, N) {
            priority_queue<PLL, vector<PLL>, greater<PLL>>pq;
            FOR(i, 0, N) { 
                pq.push(PLL(a[i], 0));
            }
            LL ret = 0;
            FOR(i, 0, N) {
                int id = (i + s) % N;
                PLL mine = pq.top(); pq.pop();
                pq.push(PLL(mine.first+b[id]/2 , mine.second+1));
                ret = max(ret, mine.second + 1);
            }
            ans = min(ret, ans);
        }
    
        cout << ans << "\n";
    
        return 0;
    }