1067 Sort with Swap(0, i)(25 分)

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], n;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        a[x] = i;
    }
    int cnt = 0, now = 1;
    while (1)
    {
        while (a[0] != 0)
        {
            swap(a[0], a[a[0]]);
            cnt++;
        }
        while (now < n&&a[now] == now)now++;
        if (now == n)break;
        swap(a[0], a[now]);
        cnt++;
    }
    printf("%d", cnt);
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 什么是独立思考?我以为,它是一种在没有任何思想禁区前提下的思维素养,这种思维素养包括以下特点:抓住中心思想和议题;...
    风儿缱绻阅读 251评论 0 0
  • 每天的六点三十分,从长郡中学学成回来的彭雄波老师会准时坐在崀山培英学校高一培英班的讲台上,指导同学们早自习。 据悉...
    亦农阅读 1,103评论 0 1
  • 我始终坚信做一个好人,一个善良的人能够取得成功获得幸福。 街头乞讨,如果真的是没有办法。只有通过这样的方...
    姜能伟阅读 979评论 0 1
  • 最近很少写一下项目总结了,最近项目虽然做了很多,但是都是一些外包项目,做下来也没有什么值得总结的。最近一个项目用到...
    gavincarter阅读 4,048评论 5 7
  • 好像我和每一个自己喜欢的女孩子都能成为好朋友,之后就能够毫不客气的被她们拒绝。每一个都说不再相信爱情,然后转身就被...
    天真烂漫傻阅读 170评论 0 0