D - AtCoder Express
Time limit : 2sec / Memory limit : 256MB
Score : points
Problem Statement
In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express.
In the plan developed by the president Takahashi, the trains will run as follows:
- A train will run for seconds.
- In the first seconds, a train must run at a speed of at most m/s (meters per second). Similarly, in the subsequent seconds, a train must run at a speed of at most m/s, and so on.
According to the specifications of the trains, the acceleration of a train must be always within . Additionally, a train must stop at the beginning and the end of the run.
Find the maximum possible distance that a train can cover in the run.
Constraints
- All input values are integers.
Input
Input is given from Standard Input in the following format:
…
…
Output
Print the maximum possible that a train can cover in the run.
Output is considered correct if its absolute difference from the judge's output is at most .
Sample Input 1
1
100
30
Sample Output 1
2100.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first seconds, it accelerates at a rate of , covering meters.
- In the subsequent seconds, it maintains the velocity of , covering meters.
- In the last seconds, it decelerates at the acceleration of , covering meters.
The total distance covered is + + = meters.
Sample Input 2
2
60 50
34 38
Sample Output 2
2632.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first seconds, it accelerates at a rate of , covering meters.
- In the subsequent seconds, it maintains the velocity of , covering meters.
- In the subsequent seconds, it accelerates at a rate of , covering meters.
- In the subsequent seconds, it maintains the velocity of , covering meters.
- In the last seconds, it decelerates at the acceleration of , covering meters.
The total distance covered is + + + + = meters.
Sample Input 3
3
12 14 2
6 2 7
Sample Output 3
76.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first seconds, it accelerates at a rate of , covering meters.
- In the subsequent seconds, it maintains the velocity of , covering meters.
- In the subsequent seconds, it decelerates at the acceleration of , covering meters.
- In the subsequent seconds, it maintains the velocity of , covering meters.
- In the last seconds, it decelerates at the acceleration of , covering meters.
The total distance covered is + + + + = meters.
Sample Input 4
1
9
10
Sample Output 4
20.250000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first seconds, it accelerates at a rate of , covering meters.
- In the last seconds, it decelerates at the acceleration of , covering meters.
The total distance covered is + = meters.
Sample Input 5
10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70
Sample Output 5
20291.000000000000 //题意:读了老半天,就是说一列火车在 n 段路上行驶,给出行驶的时间,和最大速度限制,起点终点速度要为 0 ,问最大可行驶的路程是多少?
//应该是头次做这种题吧, 所以,做的比较慢,先逆序扫一遍,可得到在每段路上行驶,为了到终点为 0 速度,限制速度是多少。
然后正序累加,具体操作是,二分(加速时间+匀速时间)的最大值,然后就可以轻松解决了
# include <bits/stdc++.h>
using namespace std;
# define eps 1e-
# define INF 1e20
# define pi acos(-1.0)
# define MX
struct Node
{
double t,v;
double ev; //从终点的最大速度
}seg[MX]; int n;
double spd, ans; void gogo(int x)
{
double l=, r=seg[x].t;
double res = ;
while (l<r-eps) // <
{
double mid = (l+r)/;
if (mid + spd > seg[x].v-eps)
{
if ((seg[x].v - seg[x+].ev) + mid < seg[x].t+eps)
{
res = mid;
l = mid;
}
else r = mid;
}
else
{
if (mid + spd - (seg[x].t-mid) - seg[x+].ev < -eps) //<=
{
res = mid;
l = mid;
}
else r = mid;
}
} double jia, yun, jian;
if (spd + res < seg[x].v)
{
jia = res;
yun = ;
jian = seg[x].t - jia;
}
else
{
jia = seg[x].v - spd;
yun = res - jia;
jian = seg[x].t - jia - yun;
}
ans += 1.0/2.0*jia*jia + spd * jia;
ans += yun * seg[x].v; if (res+spd < seg[x].v)
{
ans += -1.0/2.0*jian*jian + (spd+jia) * jian;
spd = spd + jia - jian;
}
else
{
ans += -1.0/2.0*jian*jian + seg[x].v * jian;
spd = seg[x].v - jian;
} } int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%lf",&seg[i].t);
for (int i=;i<=n;i++)
scanf("%lf",&seg[i].v);
spd=0.0;
for (int i=n;i>=;i--)
{
if (spd+seg[i].t < seg[i].v+eps) //<=
spd += seg[i].t;
else
spd = seg[i].v;
seg[i].ev = spd;
}
ans = ;
spd = ;
seg[n+] = (Node){0.0, 0.0, 0.0}; for (int i=;i<=n;i++)
{
gogo(i);
}
printf("%.5f\n",ans);
return ;
}