本文最后更新于 2024年9月7日 下午
洛谷题目传送门 | AT 原题传送门
思路
分析题目可以很简单地得到,如果满足 pi=i 的条件,那么交换 pi 和 pi+1 后得到的结果一定是最优解。
我们要做的只是从前到后遍历一遍 p 数组,如果 pi=i 就交换 pi 和 pi+1,同时 ans 累加。
看到楼下有大佬说当 i=n 是需要特判,但其实完全不需要,只要数组开的够大,也不会在交换 pn 和 pn+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]); } } printf("%d\n",ans); return 0; }
|