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
|
using namespace std;
const int maxn = 1e6+5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
typedef long long ll;
#define pb push_back
struct {
double price;
int dis;
bool operator < (const node& b) {
return dis > b.dis;
}
}a[maxn];
vector<node> v;
bool cmp (const node&a,const node&b) {
return a.dis < b.dis;
}
bool vis[maxn]={false};
int main() {
#ifdef ONLIGE_JUDGE
#else
#endif
int c,dis,run,n,tmpD = 0;
double res = 0,tmpP = -1,tmpC = 0;
cin >> c >> dis >> run >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i].price >> a[i].dis;
if (a[i].dis == 0) tmpP = a[i].price;
}
if (tmpP < 0) {
return printf("The maximum travel distance = %.2fn",(double)tmpD),0;
}
sort(a,a+n,cmp);
node d;d.dis = dis;
a[n] = d;
int j = 0;
while (tmpD < dis) {
int maxDis = tmpD + c * run;
v.clear();
for (int i = 1; i <= n; ++i)
if (tmpD < a[i].dis && maxDis >= a[i].dis) {
v.pb(a[i]);
}
if (v.size()) {
j = 0;
while (v[j].price > tmpP) j++;
if (j >= v.size()) {
j = min_element(v.begin(),v.end()) - v.begin();
if (v[j].dis == dis) {
res += (v[j].dis - tmpD) / (double)run * tmpP;
} else {
res += (c - tmpC) * tmpP;
tmpC = c - (v[j].dis - tmpD) / (double)run;
}
tmpD = v[j].dis;
tmpP = v[j].price;
} else {
tmpC -= (v[j].dis - tmpD) / (double)run;
if (tmpC < 0) {
res += fabs(tmpC) * tmpP;
tmpC = 0;
}
tmpD = v[j].dis;
tmpP = v[j].price;
}
} else {
printf("The maximum travel distance = %.2fn",(double)maxDis);
break;
}
} if (tmpD >= dis) {
printf("%.2fn",res);
}
return 0;
}
|
近期评论