[白俊1826]燃料を満タンにする

燃料充填1826
を選択します.

グリンディ

に答える
できるだけガソリンスタンドに行く回数を減らすので、今燃料で行けるガソリンスタンドの中で、できるだけ遠くのガソリンスタンドやガソリンスタンドに行くときに、燃料が一番多ければ2つの中で1つだけ行ってこそ、最小限の状況を見つけることができると思います.
まず、現在の燃料で一番遠いところに行くと言ったら
N = 2 L = 14 P = 4
(2,3) (4,7)
この例では、−1が出力される.現在、燃料4が最も遠い場合は4番ガソリンスタンドに行くのですが、そうすると、到着点14の燃料が足りなくなります.そのため、現在燃料から最も遠いガソリンスタンドに行く方法は間違っています.
第二に、現在利用可能な燃料のガソリンスタンドの中で、充電時に燃料が最も多い場合を考えてみましょう.
より詳細には、現在行けるガソリンスタンドの中で、最も燃料が得られる順番を選択します.上記の例では、現在最も燃料が多いのは4番ガソリンスタンドです.4日に行った時は燃料が7で、まだ到着点14に着けませんでした.でも4番のガソリンスタンドの前に2番のガソリンスタンドに行って、4番のガソリンスタンドに行ったら、全部で10の燃料がもらえて、到着点14まで.
では、どのように実施すればいいのでしょうか.まず、現在の位置に燃料を使って行けるガソリンスタンドのガソリン代をすべて貯蔵します.次に、最大値から、次のポイントに到達できるかどうかを決定します.行けない場合は、最大値を外し、燃料を加えて、次の場所に行けるかどうかを確認します.この手順を繰り返し、保存した値がないが次の点に到達できない場合は、終点に到達できないことを意味するので、-1を出力します.そうでなければ、保存した値から1つ抽出すれば、カウントして正解として出力できます.格納された値は常に最大値を直接知る必要があるため、最大hipを使用して迅速に取得できます.
コード#コード#

#include <bits/stdc++.h>
using namespace std;


int n, l, p;
pair<int, int> v[10001];
priority_queue<int> pq;

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
	}
	cin >> l >> p;

	sort(v, v + n);
	
	int i = 0, ans = 0;
	bool out = false;

	while (p < l) {
		while (i < n && p >= v[i].first) {
			pq.push(v[i].second);
			i++;
		}

		if (pq.empty()) {
			out = true;
			break;
		}

		p += pq.top();
		pq.pop();
		ans++;
	}

	cout << (out ? -1 : ans);

	return 0;
}