【题解】特别排序法

题意

给你一个有个不同元素的序列，你可以选着一些子序列对子序列内部进行排序，排序后将数放回所取的子序列对应位置，问最多可以去多少个子序列完成排序后使得整个序列递减。

题解

考虑排完序后位置上的数应该是。所以对于位置来说是一定要把加入到这个子序列中的，那么我们找到这个数所在的位置记为，那么我们还需要把这个数加入到子序列中，所以一直重复这个过程，最终会形成一个环，即一组子序列。那么我们做几次这样的，也就表示了最多可以划分多少个子序列。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N], vis[N];
int n;
void dfs(int x)
{
    vis[x] = true;
    if (!vis[n-a[x]+1])
    {
        dfs(n-a[x]+1);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&a[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            dfs(i);
            ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}