题解 P2338 【[USACO14JAN]失败的滑雪Bessie Slows Down】

· · 题解

//没有什么人发题解，是不是看到 提高+/省选-被吓走了（幸好我没看到）

//思路蛮简单的(虽然我做了好久好久)，把 T和D分开存储并分别排序

//然后再是比较Ti Dj，比较Ti乘上速度加上原来走的路程和Di

//最后再把没有完成的路程所需时间加上去（然而我第一次打了时间=路程*速度，hhhhhhh）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<map>
#include<iomanip>
#include<stack>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
char chr;
double s=0,tot=0,v1,st,sd;//tot表示时间（无奈） 
int n,t[10001]={0},d[10001]={0},lt=0,ld=0,v=1;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>chr;
        if(chr=='T') cin>>t[++lt];
        else cin>>d[++ld];

}//这里把T D分开读入；

    sort(t+1,t+lt+1);
    sort(d+1,d+ld+1);//排序不讲 
    d[ld+1]=0x3f3f3f3f;
    t[lt+1]=0x3f3f3f3f;//重点：如果没有这里的话，下面的i和j可能一个永远不变，一个一直加1； 
    int i=1,j=1;
    while(i<=lt||j<=ld)
    {
        v1=1.0/v;//算速度； 
        st=s+(t[i]*1.0-tot)*v1;//用Ti的时间 
        sd=d[j];//用Dj的时间 
        if(st<sd)
        {
            s=st;//更新路程 
            tot=t[i];//这里不要 路程/速度，可能会有精度问题 （我也没试过） 
            i++;
        }
        else
        {
            tot+=(sd-s)/v1;
            s=sd;
            j++;
        }
        v++;//时间的分母++； 
    }
    tot+=(1000-s)/(1.0/(v*1.0));//最后再把没有完成的路程所需时间加上去 
    cout<<int(tot+0.5);//四舍五入噢！ 
    return 0;
}