cogs 1945. 奶牛跑步

★   输入文件：cowjoga.in   输出文件：cowjoga.out   简单对比
时间限制：1 s   内存限制：256 MB

【题目描述】

奶牛们又兴高采烈地出去运动了！一共有N(1 <= N <= 100,000)头牛在一条无限长的单向羊肠小道上慢跑。每头牛在小道上的起点都不同，牛儿们的速度也不尽相同。

这条羊肠小道太窄了，奶牛们没办法"超车"，如果一头快速牛追上了前边的慢速牛，她就必须减速，从而融入这些慢速牛集团中，变成跟前面的牛一样的速度。

牛儿们一共要跑T(1 <= T <= 1,000,000,000)分钟，请帮FJ计算一下，当时间结束时，牛儿们一共会形成多少个集团。

【输入格式】

第一行有两个整数N和T；

接下来有N行，每行有两个数，第一个数是一个非负整数，表示一头牛的起始位置，第二个数是一个正整数，表示该牛的速度；两个数均不超过10^9，所有的牛起始位置都不同，所以输入文件是以起始位置升序的方式给出数据。

【输出格式】

输出一个整数，表示T分钟后的集团数。

【样例输入】

5 3
0 1
1 2
2 3
3 2
6 1

【样例输出】

3

//从第n头奶牛开始枚举，若之前奶牛终点<之后奶牛终点 ，ans++； 

#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define LL long long

using namespace std;
const int maxn=105000;

struct Node {
    LL set,speed;
} a[maxn];

int n,t;

void Init() 
{
    scanf("%d%d",&n,&t);
    LL date,last=0,tot=1;
    for(int i=1; i<=n; i++)scanf("%lld%lld",&a[i].set,&a[i].speed);
    for(int i=n; i>=1; i--) 
    {
        date=a[i].speed*t+a[i].set;
        if(i==n) 
        {
            last=date;
            continue;
        }
        if(date<last)tot++,last=date;
    }
    printf("%lld
",tot);
}

int main() 
{
    freopen("cowjoga.in","r",stdin);
    freopen("cowjoga.out","w",stdout);
    Init();
    return 0;
}