2014年12月30日 星期二

USACO 2014 December Contest, Silver Problem 3. Cow Jog

// http://www.usaco.org/index.php?page=viewproblem2&cpid=493
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const long double INF = 2000000000;

typedef long double ld;

typedef pair<ld, int> ti;
#define t first
#define i second

typedef pair<int, int> xv;
#define x first
#define v second

xv cow[200000];

ld tme[200000];
int past[200000];
int N, T;

set<ti> s;

int main()
{
    freopen("cowjog.in", "r", stdin);
    freopen("cowjog.out", "w", stdout);
    
    scanf("%d %d", &N, &T);
    
    for(int Ni = 0; Ni < N; Ni++)
        scanf("%d %d", &cow[Ni].x, &cow[Ni].v);
        
    for(int Ni = 0; Ni < N; Ni++)
        past[Ni] = Ni-1;
    
    tme[0] = INF;
    s.insert(ti(INF, 0) ); 
       
    for(int Ni = 1; Ni < N; Ni++)
    {
        int Nj = past[Ni];
        
        if( ld(cow[Nj].v-cow[Ni].v)*INF > cow[Ni].x-cow[Nj].x ) 
        {
            ld p = ld(cow[Ni].x-cow[Nj].x)/(cow[Nj].v-cow[Ni].v);
            tme[Ni] = p;
            s.insert(ti(p, Ni) );     
        } 
        else 
        {
            tme[Ni] = INF;
            s.insert(ti(INF, Ni) );  
        }
    }
    
    int cnt = N;
    
    while( !s.empty() )
    {
        ti F = *s.begin();
        if( F.t > T ) break;
        
        s.erase(s.begin() ); cnt--;
        
        int Ni = past[F.i];
        s.erase(ti(tme[Ni], Ni) );    
        
        past[F.i] = past[Ni];
        Ni = F.i;
        
        if( past[Ni] != -1 )
        {
            int Nj = past[Ni];
            
            if( ld(cow[Nj].v-cow[Ni].v)*INF > cow[Ni].x-cow[Nj].x ) 
            {
                ld p = ld(cow[Ni].x-cow[Nj].x)/(cow[Nj].v-cow[Ni].v);
                tme[Ni] = p;
                s.insert(ti(p, Ni) );     
            } 
            else 
            {
                tme[Ni] = INF;
                s.insert(ti(INF, Ni) );  
            }
        }
        else
        {
            tme[Ni] = INF;
            s.insert(ti(INF, Ni) ); 
        }
    }
    
    printf("%d\n", cnt);
}

沒有留言:

張貼留言