签订协议

题目链接：nowcoder 217601

到主站看：https://blog.csdn.net/weixin_43346722/article/details/113064299

题目大意

有一个每个数都不相同的数组，然后要从最大值不停地选取数，然后每次只能从左往右扫过去，碰到的要拿的才能拿。
问你至少要弄多少次才可以点完所有数，如果扫到一半数玩了所有数，最后扫的那一次也要算上。

思路

这道题看到这个，我们考虑直接模拟。

当然，不是模拟它扫的过程，而是枚举每个数被选的过程。

那我们先按数被选的先后顺序排序。
那怎么看要不要在轮，轮几次呢？
因为问你是在最优条件下，那只要碰到了就一定会选。那也就是说最多只会轮一次。因为你轮一次，就可以保证每个点都跑了一遍，就必定会跑到你要的点。
我们只要看从上一个数到这个数不停往右移动的时候会不会碰到边界要从第一个继续搜就可以了。
那怎么看呢？容易想到是当这个数的位置在你上一个选的数的位置的前面。

那我们就在排序的时候，记录下每个数一开始时的位置。

然后因为最后扫完的时候那一次也要算上，所以答案要加一。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

struct country {
    int x, num;
}a[800001];
int n, ans, now;

bool cmp(country x, country y) {
    return x.x > y.x;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].x);
        a[i].num = i;//记录原来的位置
    }

    sort(a + 1, a + n + 1, cmp);//先按选择先后顺序排序

    for (int i = 1; i <= n; i++) {
        if (now > a[i].num) ans++;//在前面一个被选的数的前面，就是要重新轮一轮
        now = a[i].num;//更改当前扫到哪个地方
    }

    printf("%d", ans + 1);//因为不管你最后扫没扫完，最后那一次都要算，所以要加上1

    return 0;
}