青海省住房和城乡建设部网站,有创意的图文广告店名,网站定制开发上海,沧州百度推广总代理题干#xff1a;
妞妞得到一个(1~n)的排列p1, p2, p3,...,pn, 听村里的老人牛牛说如果让这个排列变为:
对于所有的1 i n, 都满足pi ≠ i, 就可以获得Google Girl Hackathon的入场券。 妞妞仅允许的操作是: 交换排列中两个相邻的元素, 并且妞妞允许做这个操作任意…题干
妞妞得到一个(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代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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()
{cinn;for(int i 1; in; i) scanf(%d,ai);for(int i 1; in-1; i) {if(a[i] i) {swap(a[i],a[i1]);ans;}}if(a[n] n) ans;printf(%d\n,ans);return 0 ;}别忘判断最后一个元素虽然不判断也可以AC那是因为样例水了。
