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 階の区間で最大の体力）以下になります。
よって、実際の回復量を求めるためには、区間の最大値を求める必要があることがわかります。
方針
使うもの 優先度キュー、 セグメントツリー（区間に対する加算、 区間の最小値を求める）
１）体力をセグメントツリーに記録する ２）泉の情報をキューに入れる ３）体力を消費する ４）体力が0以下になったとき １）最も回復量が多いものを取り出す ２）区間[回復する場所、現在地]の最大値を求める ３）体力の最大値 + 回復量 <= 体力の上限 のとき、その泉を使えるだけ使う。 使えないとき、実際の回復量を更新してキューに戻す。その後、1に戻る ４）泉を使って回復したことにし、区間に加算する。
実装
#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;
}