AOJ 0553 ダンジョンの解説
AOJ 0553 ダンジョン
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553
考察
問題点
あり本にある優先度キューを用いたガソリン問題と似ています。
ただし、こちらの問題では、ガソリンを入れられる量の上限があります。
体力が0以下になる前に、どこかで回復しなければいけない
->どうせ回復するなら一番回復量が多い泉を使いたい
->体力が0以下になった時に、最も回復量が高い泉を使ったことにすれば良い
これは優先度キューを用いれば実現できそうです。
やっかいなのは体力の上限で、「泉の回復量は多いが、体力が減っていないため、実際の回復量が小さくなる」ということが起きるため、優先度キューだけを用いてもうまくいきません。
「泉の回復量が多い順」ではなく、「実際の回復量が多い順」に並べなければいけません。
実際の回復量は、体力と泉の回復量がわかれば求めることができそうです。
そこで、各階を訪れた際の体力を持っておき、それを元に「実際の回復量」を決めましょう。
実際の回復量を求める
体力の更新方法をまずは考えます。
地下 i 階で体力が0になったので、地下 j 階で泉を使ったことにする( i > j )。
すると、当然地下 j 階〜 i 階の体力は増えます。つまり、区間に対する加算を行う必要があります。
また、加算した際に、体力が上限を超えてはいけません。
つまり、地下 j 階で体力を回復する場合、地下 j 階〜 i 階の区間のすべての体力は、(体力の上限 - j 階の回復量)以下である必要があります。
裏を返せば、地下 j 階の回復量は、(体力の上限 - 地下 j 階〜 i 階の区間で最大の体力)以下になります。
よって、実際の回復量を求めるためには、区間の最大値を求める必要があることがわかります。
方針
使うもの
優先度キュー、 セグメントツリー(区間に対する加算、 区間の最小値を求める)
1)体力をセグメントツリーに記録する
2)泉の情報をキューに入れる
3)体力を消費する
4)体力が0以下になったとき
1)最も回復量が多いものを取り出す
2)区間[回復する場所、現在地]の最大値を求める
3)体力の最大値 + 回復量 <= 体力の上限 のとき、その泉を使えるだけ使う。
使えないとき、実際の回復量を更新してキューに戻す。その後、1に戻る
4)泉を使って回復したことにし、区間に加算する。
実装
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; //const int INF = 1e8; using namespace std; #define int long long const int MAX_N = 100010; class segTree{ public: int n, dat[4 * MAX_N]; void init(int n_, int value, int dat_b[4 * MAX_N] = NULL){ n = 1; while(n < n_) n *= 2; rep(i,2 * n){ dat[i] = value; if(dat_b != NULL) dat_b[i] = value; } } void output(int a[4 * MAX_N]){ show("print"); range(i,1,n * 2) cout << (a[i] == INT_MAX ? 0 : a[i]) << ' '; cout << endl; } }; class starrySky : public segTree{ private: int query(int a, int b, int k, int l, int r){ if(b <= l || r <= a) return 0; if(a <= l && r <= b) return dat[k] + dat_add[k]; int vl = query(a, b, k * 2, l, (l + r) / 2); int vr = query(a, b, k * 2 + 1, (l + r) / 2, r); return max(vl, vr) + dat_add[k]; } void add(int a, int b, int k, int l, int r, int x){ if(b <= l || r <= a) return; if(a <= l && r <= b){ dat_add[k] += x; }else{ add(a, b, k * 2, l, (l + r) / 2, x); add(a, b, k * 2 + 1, (l + r) / 2, r, x); dat[k] = max(dat[k * 2] + dat_add[k * 2], dat[k * 2 + 1] + dat_add[k * 2 + 1]); } } void init(int n_){ segTree::init(n_,0,dat_add); } public: int dat_add[4 * MAX_N]; starrySky(int n){ init(n); } int query(int a, int b){ return query(a, b, 1, 0, n); } void add(int s, int t, int x){ add(s, t, 1, 0, n, x); } void add(int i, int x){ add(i, i + 1, 1, 0, n, x); } }; signed main(){ long long n, h; cin >> n >> h; //1-indexのセグ木 starrySky seg(n); //体力を保持する priority_queue<pair<long long, int>> q; //泉の回復量、pos long long cur = h, ans = 0; rep(i,n - 1){ long long damage, heal; cin >> damage >> heal; q.push(make_pair(heal, i)); seg.add(i + 1, cur); cur -= damage; while(cur <= 0){ pair<long long, int> use = q.top(); q.pop(); long long maxHP = seg.query(use.second + 1, i + 2); //回復地点から現在地までの体力の最大 if(maxHP + use.first > h){ //回復量が上限を超えるので、実際の回復量に変更 q.push(make_pair(h - maxHP, use.second)); continue; } long long can_use = (h - maxHP) / use.first; long long require = ceil((-1.0 * cur + 1) / use.first); long long used = min(can_use, require); ans += used; cur += used * use.first; seg.add(use.second + 1, i + 2, used * use.first); q.push(use); } } cout << ans << endl; }