T259435 Jog S

· · 个人记录

jog S传送门

题目描述

有N (1 <= N <= 100,000)头奶牛在一个单人的超长跑道上慢跑，每头牛的起点位置都不同。由于是单人跑道，所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候，他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。

请计算T (1 <= T <= 1,000,000,000)时间后，奶牛们将分为多少小组。

输入格式

第一行包含两个数字n,t 接下来的n行，表示每头牛的位置和速度 位置是非负数，速度是正数 位置按照升序排列

输出格式

t时间后，一共有几组牛

样例 #1

样例输入 #1

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

样例输出 #1

3

思路：在最开始的时候求出每头牛在t秒的位置（最终位置），如果后一头牛追上了前一头牛，无视它，把它们看成一个整体。

注意：1 <= T <= 1,000,000,000所以用long long

代码：

#include<bits/stdc++.h>
using namespace std;
int n,cnt=1;
long long t,last[100010];
struct people{
    int d;
    int v;
}a[100010];
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].d,&a[i].v);
        last[i] = a[i].d+a[i].v*t;
    }
    long long la = last[n];
    for(int i=n-1;i>=1;i--){
        if(last[i] < la){
            la = last[i];
            cnt++;
        }
    }
    printf("%d",cnt);
    return 0;
}