[BZOJ3431]&&[Usaco2014 Jan] Bessie Slows Down

描述 Description

[Brian Dean, 2014] Bessie the cow is competing in a cross-country skiing event at the winter Moolympic games. She starts out at a speed of 1 meter per second. However, as she becomes more tired over time, she begins to slow down. Each time Bessie slows down, her speed decreases: she moves at 1/2 meter per second after slowing down once, then 1/3 meter per second after slowing down twice, and so on. You are told when and where Bessie slows down, in terms of a series of events. An event like this:

T 17

means that Bessie slows down at a specific time – here, 17 seconds into the race. An event like this:

D 10

means that Bessie slows down at a specific distance from the start – in this case, 10 meters. Given a list of N such events (1 <= N <= 10,000), please compute the amount of time, in seconds, for Bessie to travel an entire kilometer. Round your answer to the nearest integer second (0.5 rounds up to 1).

奶牛的初始速度为 1m/s, 第 i 次减速后速度为 1/(i+1) m/s, 给出给定 N 次减速事件，T x 表示在 x 秒减速，D x 表示在离起点 x 米处减速，减速事件不以时间顺序给出，并且可能同时发生，问跑完 1000 米所用时间

输入格式 InputFormat

Line 1: The value of N.

Lines 2..1+N: Each line is of the form “T x” or “D x”, indicating a time event or a distance event. In both cases, x is an integer that is guaranteed to place the event before Bessie reaches one kilometer of total distance. It is possible for multiple events to occur simultaneously, causing Bessie to slow down quite a bit all at once. Events may not be listed in order.

输出格式 OutputFormat

Line 1: The total time required for Bessie to travel 1 kilometer.

样例输入 SampleInput

5
T 784
T 1083
D 336
D 792
D 302

样例输出 SampleOutput

3547

来源 Source

Silver

BZOJ 3431

注意输出时四舍五入。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
double tim[200005],dis[200005];
double ans,nv,nd,nt;
char ch[10];
inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
int main()
{
    //freopen("dig.in","r",stdin);
    //freopen("dig.out","w",stdout);
    l=r=0;
    read(n);m=1000;
    for (i=1;i<=n;i++)
    {
        scanf("%s%d",ch,&x);
        if (ch[0]=='T') tim[++l]=x;
        if (ch[0]=='D') dis[++r]=x;
    }
    sort(tim+1,tim+l+1);
    sort(dis+1,dis+r+1);
    nv=1.0;nd=0.0;nt=0.0;
    x=y=1;
    while ((y<=r && dis[y]<=m) || (x<=l && nd+(tim[x]-nt)*nv<=m))
    {
        if (x<=l && (y>r || (double)tim[x]-nt<(double)(dis[y]-nd)/nv))
        {
            nd+=(tim[x]-nt)*nv;
            nt=tim[x];
            x++;
            nv=(double)1/(x+y-1);
        }
        else if (y<=r)
        {
            nt+=(dis[y]-nd)/nv;
            nd=dis[y];
            y++;
            nv=(double)1/(x+y-1);
        }
    }
    ans=nt;
    if (nd<m)
    {
        ans+=(double)(m-nd)/nv;
    }
    if (nd>m)
    {
        ans-=(double)(nd-m)/(1/(x+y-2));
    }
    printf("%.0lf\n",ans);
    return 0;
}