luogu P3111 [USACO14DEC]牛慢跑Cow Jog_Sliver |贪心+模拟

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

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


#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
#define ll long long
ll now[N];
ll T,n;
int main(){
	cin>>n>>T;
	for(ll i=1,x,v;i<=n;i++){
		scanf("%lld%lld",&x,&v);
		x-=1e9;
		now[i]=x+v*T;
	}
	ll ans=1;
	for(int i=n-1;i>=1;i--){
		if(now[i]>=now[i+1])
		now[i]=now[i+1];
		else ans++;
	}
	cout<<ans<<endl;
}
不以物喜,不以己悲
原文地址:https://www.cnblogs.com/naruto-mzx/p/11855533.html