签订协议

nowcoder 217601

题目大意

给出n个数，现在有一个协议书，让你从1传到n，然后传回1，继续传下去
对于第i个数，如果前面i-1个数已经匹配过了，那么当协议书传过来时即可匹配，否则无法匹配
我让你让所有数匹配最少传多少圈（向上取整）

解题思路

如果直接暴力枚举会TLE
当匹配完值为的点后需要匹配值为的点
那么可以按排序，这样得到匹配的数的顺序
设为当前数的初始位置
如果那么不用多传一圈
否则要多传一圈

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, ans;
struct node
{
    int v, s;
}a[800010];
bool cmp(node x, node y)
{
    return x.s > y.s;//按给出的值排序
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i].s);
        a[i].v = i;//记录初始位置
    }
    sort(a + 1, a + 1 + n, cmp);//排序
    for (int i = 2; i <= n; ++i)
        if (a[i].v < a[i - 1].v)//要多传一圈
            ans++;
    ans++;//不满一圈的
    printf("%d", ans);
    return 0;
}