11551: 【原1551】跑步还是组团的好

题目

题目描述

author: USACO Olympaid 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1551

Description

N个好朋友们约定好一起慢跑，约定好了路线和时间，不过因为宿舍位置不一样所以大家起点也不一样，因为每个人能力不一样所以速度也不一样。所以大家商量好了，如果后面的人追上了前面的人，就降速和前面的人保持一样的速度一起跑，所以跑到足够长时间以后，大家跑成了一个个小团体。不过这些小团体一共有多少个呢？

Input Format

共(N+1)行。

第1行：N(1<=N<=10000000)，代表总人数。

第2~(N+1)行：每行2个整数，P, V(1<=P,V<=10000000).

其中P代表起始位置，V代表跑步速度。

Output Format

一个整数，代表最后的团体书。

Sample Input

5
0 1
1 2
2 3
3 2
6 1

Sample Output

2

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int vnow=0x3f3f3f3f,n,ans,p;
int main() {
    int *v;
    scanf("%d",&n);
    v=new int[n];
    for (int i=0;i<n;++i)
        scanf("%d %d",&p,&v[i]);
    for (int i=n-1;i>=0;--i)
        if (v[i]<=vnow){
            ans++;
            vnow=v[i];
        }
    printf("%d",ans);
    return 0;
}

yyong119's solution

#include <cstdio>
#include <stack>
#define MAX_N 10000010
using namespace std;
int n, tmp;
// int v[MAX_N];
stack<int> v_non_inc;
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
int main() {
    n = read();
    // for (register int i = 0; i < n; ++i)
    //     v[read()] = read();
    for (register int i = 0; i < n; ++i) {
        read(); tmp = read();
        while (!v_non_inc.empty() && v_non_inc.top() > tmp)
            v_non_inc.pop();
        v_non_inc.push(tmp);
    }
    // int ans = 0, v_last = 0x7fffffff;
    // for (register int i = MAX_N - 1; i >= 0; --i) {
    //     if (!v[i]) continue;
    //     if (v[i] <= v_last) {
    //         ++ans;
    //         v_last = v[i];
    //     }
    // }
    // printf("%d", ans);
    printf("%d", v_non_inc.size());
    return 0;
}