题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3893
题意：在一条无限长的跑道上有 n 头牛，每头牛有自己的初始位置及奔跑的速度。当一只牛追上另一只牛时，它们以慢牛的速度成为一个群体。求 t 分钟后一共有几个群体。
稍微修改了一下题意使得更加清楚... 需要注意的是，给出的数据是按照位置递增的.... 这在翻译中并没有体现...
从后向前扫一遍，看看能不能追上即可... 代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define N 100010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n,t,slow,ans; ll pos[N],spd[N]; int main() { n=read();t=read(); for(int i=1;i<=n;i++) {pos[i]=read(),spd[i]=read();} pos[0]=spd[0]=2100000000; for(int i=n;i;i--) { if(pos[i]+spd[i]*t<pos[slow]+spd[slow]*t) slow=i,ans++; } printf("%d",ans); return 0; } |
Comments | NOTHING