[伯俊]1826燃料補給

22117 ワード
白駿 テキストリンク
充填白準1826燃料

  • https://www.acmicpc.net/problem/1826

  • 明示的なアルゴリズムを使用してガソリンスタンドにアクセスする場合&アクセスしない場合
    ->注記キャッシュ[燃料][ガソリンスタンド]サイズ:10^6∮10^5=10^11
    ->メモリオーバーフロー

  • GRADYアルゴリズムで近づけるには
    • エラーの回答

  • 今は燃料で行ける町内の村はありません.
    現在燃料で行けるガソリンスタンドの中で得られる燃料量が一番大きいガソリンスタンドは、
    得られた燃料量が同じであれば、最寄りガソリンスタンドのGriddyアルゴリズム設計を選択する

  • 反例(https://www.acmicpc.net/board/view/29026)
    input:
    2
    2 3
    4 7
    14 4
    output: -1
    answer: 2

  • 両方のガソリンスタンドで行けるなら、
    現在設計されているグリディアルゴリズムは、到達可能な距離内のガソリンスタンドにしかアクセスできないため、村に移動することはできません.
    • #include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, L, P;
//주유소[위치] = 얻을 수 있는 연료
int station[1000000] = { 0 };
int cnt = 0;

//갈 수 있는 주유소 정렬
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second > b.second) return true;
	if (a.second == b.second) 
		return a.first > b.first;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		station[a] = b;
	}
	cin >> L >> P;

	//현재 위치
	int cur = 0;

	while (true) {
		//현재 연료로 갈 수 있는 거리 내 마을 있는 경우
		//종료
		if (cur + P >= L) {
			cout << cnt;
			break;
		}

		//현재 연료로 갈 수 있는 거리 내 마을 없는 경우
		//현재 연료로 갈 수 있는 거리 내 주유소 검사

		//<주유소 위치, 얻을 수 있는 연료양>
		vector<pair<int, int>> possibleStation;
		for (int i = cur + 1; i <= cur + P; ++i) {
			if (station[i] != 0)
				possibleStation.push_back(make_pair(i, station[i]));
		}

		//갈 수 있는 주유소 없는 경우 
		//종료
		if (possibleStation.empty()) {
			cout << -1;
			break;
		}
		
		//갈 수 있는 주유소 있는 경우
		// 1. 얻을 수 있는 연료양 가장 큰 주유소 선택 
		// 2. 얻을 수 있는 연료양이 같다면 가장 멀리 있는 주유소 선택
		sort(possibleStation.begin(), possibleStation.end(), cmp);
		
		P = P - (possibleStation[0].first - cur) + possibleStation[0].second;
		cur = possibleStation[0].first;
		cnt++;
	}

	return 0;
}
    のり

  • 現在のポイントから移動可能なアドレスをmaxheapに格納するわけではありません.
    現在の場所&現在の場所を通るガソリンスタンドをmaxheapに保存

  • 過去のガソリンスタンドなので、ガソリンスタンドに移動して消費する燃料は考慮する必要はなく、ガソリンスタンドにアクセスして得られる燃料を考慮して選択すれば良いのです
    • #include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, l, p;
//<방문 지점 위치, 방문 지점에서 얻을 수 있는 연료>
vector<pair<int, int>> stop;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		stop.push_back(make_pair(a, b));
	}
	cin >> l >> p;

	//출발 지점도 방문 지점에 포함
	stop.push_back(make_pair(0, 0));
	//마을도 방문 지점에 포함
	stop.push_back(make_pair(l, 0));
	//지점 위치 좌표 오름차순 정렬
	sort(stop.begin(), stop.end());

	//방문 주유소 수
	int cnt = 0;
	//현재 지점 & 지나쳐온 지점들에서 얻을 수 있는 연료 저장
	priority_queue<int> pastStop;

	int cur = 0;
	while(cur < stop.size()){
		//현재 위치 = 마을 위치가 되면 종료
		if (stop[cur].first == l) {
			cout << cnt;
			return 0;
		}

		pastStop.push(stop[cur].second);
		while (true) {
			//다음 지점으로 이동 가능한 경우
			if (stop[cur].first + p >= stop[cur+1].first) {
				p -= (stop[cur + 1].first - stop[cur].first);
				++cur;
				break;
			}
			//다음 지점으로 이동 불가능한 경우
			else {
				if (pastStop.empty()) {
					cout << -1;
					return 0;
				}
				++cnt;
				p += pastStop.top();
				pastStop.pop();
			}
		}
	}

	return 0;
}
    HTMLを想像しない
    MySqlテーブル文