题干：
 

妞妞得到一个(1~n)的排列p1, p2, p3,...,pn, 听村里的老人牛牛说如果让这个排列变为:

对于所有的1 <= i <= n, 都满足pi ≠ i, 就可以获得Google Girl Hackathon的入场券。

 

妞妞仅允许的操作是: 交换排列中两个相邻的元素, 并且妞妞允许做这个操作任意次。

 

但是Google Girl Hackathon就快要开始了, 妞妞希望做最少的操作就使排列满足要求, 妞妞希望你能帮助她。

输入描述:

输入包括两行, 第一行包括一个正整数n(2 <= n <= 10^5), 表示排列的长度和范围。
第二行包括n个正整数p1, p2, p3,...,pn, 即妞妞得到的排列, 保证是一个1~n的排列。

输出描述:

输出一个整数, 表示妞妞需要的操作次数。

示例1

输入

复制

5
1 4 3 5 2

输出

复制

2

解题报告：

   可以证明这样的贪心策略一定是最优的：证明方法：（起个名）同优则立证明法：也就是只要证明没有比这样更优解或者证明如果有更优解，那么我一定比他更好或者和他一样好 。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
int a[MAX],ans,n;
int main()
{
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
	for(int i = 1; i<=n-1; i++) {
		if(a[i] == i) {
			swap(a[i],a[i+1]);
			ans++;
		}
	}
	if(a[n] == n) ans++;
	printf("%d\n",ans);

	return 0 ;
 }

别忘判断最后一个元素，，虽然不判断也可以AC，，那是因为样例水了。