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;
}
上一篇:Luogu_P2886 [USACO07NOV]牛继电器Cow Relays【题解】图论 矩阵快速幂


下一篇:P1472 奶牛家谱 Cow Pedigrees