yukicoder 0009 モンスターのレベル上げ
問題文概要
問題文読んで.
制約
$1 \le N \le 1500$.
解法
「次に戦う相手」は順序付きキューに (レベル, 戦った回数) を突っ込んでおくことでわかる. あとの部分は愚直にやって, $O(n^2 \log n)$.
円環状の時は二周分持つテクが有効.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool solve(){
int n; cin >> n;
auto a = get_vec<int>(n), b = get_vec<int>(n);
b.insert(end(b), all(b));
int res = numeric_limits<int>::max();
rep(p, n){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(aur x : a) pq.emplace(x, 0);
int top = 0;
rep(i, n){
int level, battle;
tie(level, battle) = pq.top(); pq.pop();
pq.emplace(level + b[p+i]/2, ++battle);
chmax(top, battle);
}
chmin(res, top);
}
cout << res << endl;
return true;
}