whyisyoung's Blog

If you can not persist, you will never succeed :)

EOJ 1855 Solution Report - Expedition

| Comments

keywords: 贪心 (优先队列)

1. 题目描述

原题地址: EOJ 1855

又是奶牛……

一群奶牛开了一辆漏油车想去一个最近的 town (每行驶一公里漏一升油),离最近 town 的距离为 L 公里, 最初的油量为 P, 在开往 town 的途中有 N 个加油站(每个加油站的油量是 1~100 L)。

求奶牛们为了开到 town, 最少需要在几个加油站停下来加油。 如果不可能到达 town,则输出 -1。 但比较神奇的是:这辆卡车可装的油量没有上限。。。

Note:
$1 \leqslant L \leqslant 1, 000, 000 $

$1 \leqslant P \leqslant 1,000,000$

$1 \leqslant N \leqslant 10,000 $

2. 解题思路

解法一 O(n^2)

一开始想的是按照贪心的思想,每次在当前能达到的范围内找油量最多的加油站。

思想是对的,但我想错了,没考虑到每次取最多的,到了最后的话可能油量还不够,又要往回取油量次小的加油站。这样一想一想就昏了,为什么不先排个序啊!!排完序不就可以按照大小顺序取了么。

排序的规则是:

若两个加油站油量相同,则取离起点远的,否则取油量多的。

用 struct 结构体来记录每个加油站的距离(dis)和 油量(fuel),并将所有的加油站存到一个 vector 中,排序后,卡车上的总油量(total_fuel)初始化为 P,每加一次油就会增加相应的油量,从第一个开始取,若在可取的范围内 (total_fuel > L - dis ),则 total_fuel 增加,并从 vector 中删除该节点。取了该点后判断是否有 total_fuel == L,若成立则返回节点数,否则又从头开始取(因为刚刚最大的已经删掉了),若第一个不是在可取的范围内,也就是说 total_fuel 没有增加,那么就说明不能到达 town, 返回 -1。

需要注意的地方有:

  1. 题目给的是每个加油站到 town 的距离,而非加油站离起点的距离

  2. 题目给的加油站到 town 的距离不一定是排好序的(虽然这个跟本解法没多大关系)

解法二 O( nlogn )

用堆(优先队列)来维护油量

pop_heap 将 front(即第一个最大元素)移动到end的前部,同时将剩下的元素重新构造成(堆排序)一个新的heap。

push_heap 对刚插入的(尾部)元素做堆排序。

代码如下:O( $n^2$ )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// 每次在能达到的范围内油量最大的站加油,注意每停一次后,可达到的范围是动态变化的
// 先将所有加油站按照此规则排序
// 复杂度: O(n^2)
int N, L, P;

struct stop {
	int dis;
	int fuel;
};

vector<stop> vec;

int cmp(const stop &a, const stop &b)
{
	if(a.fuel == b.fuel)
		return a.dis < b.dis; // 因为 dis 是从 town 到加油站的距离,而非起点到加油站的距离
	return a.fuel > b.fuel;
}

int get_minimal_stop()
{
	int total_fuel = P;
	vector<stop>::iterator it;

	for(int ans = 0; ans < N; ++ans) {
		if(total_fuel >= L)
			return ans;

		int tmp = total_fuel;

		for(it = vec.begin(); it != vec.end(); ++it) {
			if(total_fuel >= L - it->dis) {
				total_fuel += it->fuel;
				vec.erase(it);
				break;
			}
		}
		if(tmp == total_fuel)
			// no stop was added and before this: total_fuel < L,
			// so the town is not reachable
			return -1;
	}
	return -1;
}

int main(int argc, char const *argv[])
{

	int dis, fuel;

	while(scanf("%d", &N) != EOF) {
		stop tmp;
		for(int i = 0; i < N; ++i) {
			scanf("%d%d", &dis, &fuel);
			tmp.dis = dis;
			tmp.fuel = fuel;
			vec.push_back(tmp);
		}
		scanf("%d%d", &L, &P);

		sort(vec.begin(), vec.end(), cmp);

		cout << get_minimal_stop() << endl;
	}
	return 0;
}

版本二:O( nlogn )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//
//  main.cpp
//  eoj1855_heap
//
//  Created by whyisyoung on 3/17/14.
//  Copyright (c) 2014 whyisyoung. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 10005;

int N, L, P;

struct stop {
	int dis;
	int fuel;
}Stop[maxn];

int heap[maxn];

int compare(const stop &a, const stop &b)
{
	return a.dis > b.dis;
}

int main()
{
	while(~ scanf("%d", &N)) {
		for(int i = 0; i < N; ++i) {
			scanf("%d%d", &Stop[i].dis, &Stop[i].fuel);
		}
		scanf("%d%d", &L, &P);

        sort(Stop, Stop + N, compare);

		int remain = L - P;
		int ans = 0;
		int size = 0;
		int i = 0;

		while(remain > 0) {
			for( ; i < N; ++i) {
				// 当前油用完前能经过的加油站入堆
				if(Stop[i].dis >= remain) {
					heap[size++] = Stop[i].fuel;
					push_heap(heap, heap + size);
				}
				// 若当前加油站不能入堆,则下一个也无法入堆
				else
					break;
			}

			if(size == 0) // 未经过任何一个加油站
				break;

			remain -= heap[0];
			ans++;

			// 堆顶出栈
			pop_heap(heap, heap + size);
			size--;
		}

		if(remain > 0)
			cout << -1 << endl;
		else
			cout << ans << endl;

	}

	return 0;
}

ps:这次采用了 kramdown & MathJax ,妈妈再也不用担心我的 LaTeX 公式显示不出来啦!

Reference:

LaTeX Math in Octopress

Comments