1033 To Fill or Not to Fill 25 ★★★★
很难受了，把问题想复杂了，又写了 150 行，而且还没 debug 出来，只能换了种方法。 github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：★★★★ 关键词：贪心，模拟。
题目
1033.To Fill or Not to Fill (25) With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive numbers:
Cmax(<= 100), the maximum capacity of the tank;D(<=30000), the distance between Hangzhou and the destination city;Davg(<=20), the average distance per unit gas that the car can run; andN(<= 500), the total number of gas stations. ThenNlines follow, each contains a pair of non-negative numbers:Pi, the unit gas price, andDi(<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.Output Specification:
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
Sample Input 1: 50 1300 12 8 6.00 1250 7.00 600 7.00 150 7.10 0 7.20 200 7.50 400 7.30 1000 6.85 300
Sample Output 1: 749.17
Sample Input 2: 50 1300 12 2 7.10 0 7.00 600
Sample Output 2: The maximum travel distance = 1200.00
大意
公路上有 n 个加油站，每个加油站价格不一样，求设计最优加油方案，使得能到达目的地。如果不能达到目的地，请输出最远行驶距离。
思路
- 这题是贪心的题，我一开始想成线段合并的题目，一个个加油站看成线段的两端，线段长度最长 600，求 0 点出发的最大线段长度。通过线段合并，来实现最远距离的求解。
- 如果可以到达目的地，则通过价格降序依次选择加油站。如果被选择到的加油站，被现有线段包含（注意是包含，就是完全在现有线段之中）那么舍去改线段。
- 如果 margin 之后的线段能到达目的地，则不再增加加油站。（注意补 0 点）
- 确定好加油站之后，每个加油站加多少油，则是一个很大的问题。
一种考虑，如果在能行驶的距离（
Cmax×Davg）中有价格更低的，则把油加到能行驶到下一个加油站。 如果没有，则加满。
code
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int ability, d;
struct node {
int start, end;
double price;
};
struct oil {
int dis;
double price;
};
vector<node> v, m;
vector<oil> o;
bool cmpoilstart(oil a, oil b) {
return (a.dis == b.dis) ? (a.price < b.price) : (a.dis < b.dis);
}
bool cmpoil(oil a, oil b) {
return (a.price == b.price) ? (a.dis < b.dis) : (a.price < b.price);
}
bool cmpdis(node a, node b) { return a.start <= b.start; }
bool canreach() {
sort(v.begin(), v.end(), cmpdis);
for (int i = 1; i < v.size(); ++i) {
if (v[i].start > v[i - 1].end) {
return false;
}
}
int endv = v.size() - 1;
if (v[endv].end >= d) {
return true;
} else {
return false;
}
}
void margin(node temp) {
int flag = 0;
for (int i = 0; i < m.size(); ++i) {
if (m[i].start <= temp.start && m[i].end >= temp.start) {
m[i].end = temp.end;
++flag;
} else if (m[i].start <= temp.end && m[i].end >= temp.end) {
if (flag) {
m[i].start = m[i - 1].start;
m.erase(m.begin() + i - 1);
} else {
m[i].start = temp.start;
}
++flag;
}
}
if (!flag) m.push_back(temp);
}
bool lowprice(node temp) {
for (int i = 1; i < v.size(); ++i) {
if (v[i - 1].start < temp.start && v[i].start > temp.start &&
v[i - 1].price > temp.price) {
return true;
}
}
return false;
}
bool havein(node temp) {
for (int i = 0; i < m.size(); ++i) {
if (m[i].start <= temp.start && m[i].end >= temp.end) {
return false;
}
}
return true;
}
int main(int argc, char const *argv[]) {
int c, davg, n, p = 0;
cin >> c >> d >> davg >> n;
ability = c * davg;
getchar();
for (int i = 0; i < n; ++i) {
oil temp;
scanf("%lf %d", &temp.price, &temp.dis);
o.push_back(temp);
}
sort(o.begin(), o.end(), cmpoilstart);
if (o[0].dis) {
cout << "The maximum travel distance = 0\n";
return 0;
}
node first;
first.start = 0, first.end = ability, first.price = o[0].price;
v.push_back(first);
m.push_back(first);
int i = 0;
while (!o[i].dis) {
o.erase(o.begin() + i);
}
sort(o.begin(), o.end(), cmpoil);
while (p != o.size() && !canreach()) {
node temp;
temp.start = o[p].dis;
temp.price = o[p].price;
int tempend = temp.start + ability;
temp.end = (tempend > d) ? (d) : tempend;
++p;
// cout<<temp.start<<" "<<temp.end<<" "<<temp.price<<"
//"<<canreach()<<"
//"<<p<<" "<<v.size()<<" "<<m.size()<<endl;
if (havein(temp)) {
v.push_back(temp);
margin(temp);
// for(int i=0;i<m.size();++i){
// cout<<'m'<<m[i].start<<" "<<m[i].end<<endl;
// }
// for(int i=0;i<v.size();++i){
// cout<<'v'<<v[i].start<<" "<<v[i].end<<"
//"<<v[i].price<<endl;
// }
} else if (lowprice(temp)) {
v.push_back(temp);
}
}
if (p == o.size() && !canreach()) {
cout << "The maximum travel distance = " << m[0].end << endl;
} else {
int more = 0, tempstart;
double spend = 0.0;
sort(v.begin(), v.end(), cmpdis);
for (int i = 1; i < v.size(); ++i) {
tempstart = v[i].start - v[i - 1].start;
if (v[i].price <= v[i - 1].price) {
if (more < tempstart) {
spend += (tempstart - more) * v[i - 1].price * 1.0;
more = 0;
} else {
more -= tempstart;
}
} else {
if (more >= 600) {
more -= 600;
} else {
spend += (600 - more) * v[i - 1].price * 1.0;
more = 600 - tempstart;
}
}
// cout<<v[i].start<<" "<<v[i-1].start<<"
//"<<spend<<endl;
}
spend += (d - v[v.size() - 1].start - more) * 1.0 * v[v.size() - 1].price;
printf("%.2f\n", spend / davg);
}
return 0;
}
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155