/
pat1033.cpp
79 lines (75 loc) · 1.78 KB
/
pat1033.cpp
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
77
78
79
#include<iostream>
#include<algorithm>
using namespace std;
struct sta{
double price;
double pos;
}station[505];
bool cmp(const sta& a, const sta& b){
return a.pos < b.pos;
};
int main()
{
double CM,D,unit;
int N;
scanf("%lf%lf%lf%d",&CM,&D,&unit,&N);
for(int i=0;i<N;i++)
scanf("%lf%lf",&station[i].price,&station[i].pos);
station[N].price = 0;
station[N].pos = D;
sort(station,station+N+1,cmp);
double step = CM*unit;
if(station[0].pos > 0){
puts("The maximum travel distance = 0.00");
}
else{
bool flag = true;
for(int i=0;i<N;i++)
if(station[i+1].pos-station[i].pos > step){
printf("The maximum travel distance = %.2lf\n",station[i].pos+step);
flag = false;
break;
}
if(flag){
double reminder = 0;
double res = 0;
for(int i=0;i<N;){
int index = i;
double minPrice = station[i].price;
for(int j=i+1;j<=N&&station[j].pos-station[i].pos <= reminder*unit;j++)
if(station[j].price < minPrice){
index = j;
minPrice = station[j].price;
}
if(index!=i){
reminder -= (station[index].pos-station[index].pos)/unit;
i = index;
continue;
}
index = i;
for(int j = i+1;j<=N&&station[j].pos-station[i].pos<=step;j++)
if(station[j].price < minPrice){
index = j;
break;
}
if(index!=i){
res += (station[index].pos-station[i].pos-reminder*unit)/unit*station[i].price;
reminder = 0;
i = index;
}
else{
minPrice = -1;
for(int j=i+1;j<=N&&station[j].pos-station[i].pos<=step;j++)
if(minPrice==-1 || station[j].price < minPrice){
index = j;
minPrice = station[j].price;
}
res += (CM-reminder)*station[i].price;
reminder = CM-(station[index].pos-station[i].pos)/unit;
i = index;
}
}
printf("%.2lf\n",res);
}
}
}