首页 > 代码库 > cogs 1945. 奶牛跑步

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
 1 //从第n头奶牛开始枚举,若之前奶牛终点<之后奶牛终点 ,ans++; 
 2 
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<cstdlib>
 8 #include<cstdio>
 9 #define LL long long
10 
11 using namespace std;
12 const int maxn=105000;
13 
14 struct Node {
15     LL set,speed;
16 } a[maxn];
17 
18 int n,t;
19 
20 void Init() 
21 {
22     scanf("%d%d",&n,&t);
23     LL date,last=0,tot=1;
24     for(int i=1; i<=n; i++)scanf("%lld%lld",&a[i].set,&a[i].speed);
25     for(int i=n; i>=1; i--) 
26     {
27         date=a[i].speed*t+a[i].set;
28         if(i==n) 
29         {
30             last=date;
31             continue;
32         }
33         if(date<last)tot++,last=date;
34     }
35     printf("%lld\n",tot);
36 }
37 
38 int main() 
39 {
40     freopen("cowjoga.in","r",stdin);
41     freopen("cowjoga.out","w",stdout);
42     Init();
43     return 0;
44 }

 

cogs 1945. 奶牛跑步