POJ 1922 Ride to School(贪心+模拟)

题意:起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是,他有个习惯,沿途需要有人陪伴,即以相同的速度, 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时,他会以相应的速度跟上这个更快的人。先给定所有与Charley 同 路的人各自的速度与出发时间,问Charley 以这种方式跟人,骑完4500米需要多少时间。得出的结果若是小数,则向上取整。

思路;每次Charley选择的都是当前最快的单车,而且Charley最后一定是和那个最快到达Yanyuan的单车同时到达,因为最早到达的人,一定会赶上查理,而查理就会跟上他一起到达。

  无视负时间出发的单车(因为Charley还没到的时候单车就走了,如果速度比他快,他永远也追不上。速度比他慢的话,追上了也没影响), 所以我们只要看看比Charley晚出发的单车谁最快到达Yanyuan,Charley最后肯定是跟着这辆车,最后的时间就是Charley到达的时间。

一开始没仔细想,直接从追及问题上面想去了,比较麻烦。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;
const int INF=0x3f3f3f3f;
int n;
double ans;
int main()
{
    int v,t;
    double time;
    while(scanf("%d",&n),n){
        ans=INF;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&v,&t);
            if(t<0)
                continue;
            time=t+4.5/v*3600;
            ans=min(time,ans);
            //if(ans>time)
               // ans=time;
        }
        int res=ceil(ans);
        printf("%d
",res);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/chenxiwenruo/p/3321194.html