洛谷 AT3525 题解

洛谷题目传送门 | AT 原题传送门

思路

分析题目可以很简单地得到，如果满足 $p_i=i$ 的条件，那么交换 $p_i$ 和 $p_{i+1}$ 后得到的结果一定是最优解。

我们要做的只是从前到后遍历一遍 $p$ 数组，如果 $p_i=i$ 就交换 $p_i$ 和 $p_{i+1}$，同时 $ans$ 累加。

看到楼下有大佬说当 $i=n$ 是需要特判，但其实完全不需要，只要数组开的够大，也不会在交换 $p_n$ 和 $p_{n+1}$ 时发生越界情况。但为了严谨也可以特判。

完整代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p[100010];
int ans=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(p[i]==i)
		{
			ans++;//答案数量增加
			swap(p[i],p[i+1]);//交换p[i]和p[i+1]
		}
	}
	printf("%d\n",ans);
	return 0;
}