洛谷题目传送门 | AT 原题传送门
思路
分析题目可以很简单地得到，如果满足 pi=ip_i=i 的条件，那么交换 pip_i 和 pi+1p_{i+1} 后得到的结果一定是最优解。
我们要做的只是从前到后遍历一遍 pp 数组，如果 pi=ip_i=i 就交换 pip_i 和 pi+1p_{i+1}，同时 ansans 累加。
看到楼下有大佬说当 i=ni=n 是需要特判，但其实完全不需要，只要数组开的够大，也不会在交换 pnp_n 和 pn+1p_{n+1} 时发生越界情况。但为了严谨也可以特判。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #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;
}
|
