杂题——跑步

跑步

原题

小度每天早上要和小猫一起跑步。小猫的位置数值越小表示越在后面，速度越小表示越慢，它们都向一个方向跑。

小猫比较喜欢一起跑，所以当速度更快的小猫遇见速度慢的小猫时，它就会放慢速度，变成一组一起跑。注意，初始位置相同的小猫直接组成一组。

请问最终不再有追赶上的情况时，最多一组有多少只小猫？

格式

输入格式：

第一行输入的是整数 n，1≤n≤105；
接下来的n行分别包含小猫的初始位置 p 和速度 v ，1≤p,v≤108。

输出格式：

一行，一个数字，表示最多有多少小猫在一组。

样例 1

输入：

1
2
3
4
5
6
5
6 1
1 1
3 2
1 2
2 3

复制

输出：

1
3
备注

样例解释：位置速度为（3,2），（2,3）的小猫会追上（6,1）的小猫，而位置速度为（1,2）的小猫则会和（1,1）一起，所以最多三只小猫一组。

思路

​ 基本思路就是一种贪心的思路：如果第i - 1只猫速度大于第i只猫，那么无论这只猫的前面是否有猫追上它，第i-1只猫追上第i只猫的结论是不会变的！

​ 明白了这个道理这道题目的解法就非常明显了，首先按照位置从小到大排序，如果位置相同则按照速度从小到大排序，排完序之后，就是贪心思路了，从后往前枚举统计猫的堆数即可。

​ 注意：这里必须从后往前枚举，比如4 3 5 2,如果正向枚举的话，那么就只有前面两只猫可以一起走;但是如果是从后往前枚举就会发现4只猫可以全部走在一起！！！因为我们每一组猫的速度是由速度最慢的猫决定的！！！

代码

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
32
33
34
35
36
37
38
39
#include<bits/stdc++.h> 

using namespace std;
const int N = 1e5 + 10;
int n;
struct node{
    int p, v;
}ar[N];
bool cmp(node x, node y) {
    return x.p < y.p || (x.p == y.p && x.v < y.v);
}


int main( )
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> ar[i].p >> ar[i].v;

    sort(ar + 1, ar + n + 1, cmp);
    
    for (int i = 1; i < n; i++) {
        if (ar[i].p == ar[i + 1].p) ar[i + 1].v = ar[i].v;
    }
    int ans = -1, cnt = 1, index = n;
    while (1) {
        if (index - cnt == 0) break;
        if ((ar[index].p != ar[index - cnt].p && ar[index].v < ar[index - cnt].v) || ar[index].p == ar[index - cnt].p)cnt++;
        else {
            index = index - cnt;
            cnt = 1;
        }
        ans = max(ans, cnt);
    }

    cout << ans;
    return 0;
}