模拟：

JOG 20200807 普及模拟赛题

漫步（jog.cpp/c/pas）

（1s，512MB）

【题目描述】

  有 n 组人在一条无尽的小路上漫步，每组人都有一个初始位置和速度，一组人总是会以相同的速度进行漫步，且所有人漫步的方向都相同。

因为这是一条小路，所以当一个速度更快的赶上另一组速度较慢的人时，这两组会合并成一组，而合并成的这个新组的速度与原来两组中速度较慢的那组速度相同，他们会以这个速度继续往前跑。

当然跑到最后的时候，没有任何一组会与其他组再合并。这个时候还剩下几组人？

【输入格式】

第一行两个数 n，表示初始组数。

接下一行 n 行每行两个数 d、v，表示这组的初始位置和初始速度。

数据保证所有组初始位置不同，并且读入按从小到大的顺序给出。

【输出格式】

一行一个数 ans , 表示最后还剩下几组。

【样例输入】

5

0  1

1  2

2  3

3  2

6  1

【样例输出】

2

【数据范围】

对于 30 % 的数据，n ≤ 2000。

对于 100 % 的数据，n ≤ 10^5，0 ≤ d ≤ 10^9，1 ≤ v ≤ 10^9。

模拟写法：

#include<cstdio>
using namespace std;
int n,v[100005],ans=1,x;
int main(){
    freopen("jog.in","r",stdin);
    freopen("jog.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%*d%d",&v[i]);
    x=v[n];
    for(int i=n-1;i;--i)
        if(v[i]<=x) ++ans,x=v[i];
    printf("%d",ans);
    return 0;
}

单调队列入门：

#include <bits\stdc++.h>
using namespace std;

const int kMaxn = 111111;

int n, a[kMaxn], top = 0;

int main() {
    freopen("jog.in", "r", stdin);
    freopen("jog.out", "w", stdout);
    scanf("%d", &n);
    while (n--) {
        int t;
        scanf("%*d%d", &t);
        while (top && t < a[top]) {//维护一个单调不降的队列，最终队列里元素的个数就是答案
            --top;//例如：1 2 3 3，说明可定都追不上
        }
        a[++top] = t;
    }
    printf("%d\n", top);
    return 0;
}

P3111 [USACO14DEC]Cow Jog S

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

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,t,last[100005];
struct cow{
    long long x,v;
}a[100005];
int main(){
    cin >> n >> t;
    for(int i=1;i<=n;i++){
        cin >> a[i].x >> a[i].v;
        last[i]=a[i].x+a[i].v*t;
    }
    long long res=1, la = last[n];//long long 
    for(int i=n-1;i>=1;i--){
        if(last[i] < la){
            la = last[i];
            res++;
        }
    }
    cout<< res<<endl;
    return 0;
}