pat 1033 to fill or not to fill

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
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
#include <cstdio>
#include <algorithm>
#define MAX 510
#define INF 1000000000
using namespace std;
int cmax , d, davg , n;
struct Stop
{
double price;
double dis;
}s[MAX];
bool cmp(Stop a , Stop b)
{
return a.dis < b.dis;
}
int main()
{
scanf("%d%d%d%d" , &cmax , &d , &davg , &n);
int i , j;
for(i = 0 ; i < n ; ++i)
{
scanf("%lf%lf" , &s[i].price , &s[i].dis);
}
s[n].price = 0;
s[n].dis = d;
sort(s , s + n , cmp);
if(s[0].dis != 0)
{
printf("The maximum travel distance = 0.00");
return 0;
}
int now = 0;
double cost = 0;
int nowdis = 0;
double nowTank = 0;
while(now < n)
{
int next = -1 ;
double min = INF;
for(j = now+1 ; j <= n ; ++j)
{
if(s[j].price < min && (s[j].dis <= (s[now].dis + cmax * davg)))
{
min = s[j].price;
next = j;
if(min < s[now].price)
break;
}
}
if(next == -1)
{
break;
}
double need = (s[next].dis - s[now].dis) / davg;
nowdis += s[next].dis - s[now].dis;
/* if(min < s[now].price)
{
if(nowTank < need)
{
cost += (need - nowTank) * s[now].price;
nowTank =0;
}
else
{
nowTank -= need;
}
}
else
{
cost += (cmax - nowTank) * s[now].price;
nowTank = cmax - need;
}*/
if(need > nowTank)
{
if(min < s[now].price)//加至刚好能到达下站的油
{
cost += (need - nowTank) * s[now].price;
nowTank = 0;
}
else
{
cost += (cmax - nowTank) * s[now].price;//下一站贵,这站加满先
nowTank = cmax - need;//一定要减去用了的
}
}
else
{
nowTank -= need;
}
now = next;
}
//printf("%.2f\n" , cost);
if(now == n)
{
printf("%.2f\n" , cost);
}
else
{
printf("The maximum travel distance = %.2f\n" , s[now].dis + cmax * davg);
}
return 0;
}

热评文章