yy1158047452
我像风一样自由~
采纳率35.7%
2020-03-13 23:12

求大佬帮忙写个简单正确得代码,这是一个排序的题,感谢,等我有币了一定奉上

已采纳

问题 W: [深入浅出学算法][排序专题] 徒弟们的逆袭
时间限制: 1 Sec 内存限制: 128 MB
提交: 62 解决: 6
[提交] [状态] [讨论版] [命题人:tpengshuhai]
题目描述
排序大师有n个徒弟,分别是1徒弟,2徒弟,3徒弟……n徒弟。在前几次的测验中,每个人都有考试分数a[k],师傅想知道有多少徒弟逆袭了他的师兄?因此,无论目前你的成绩如何,竭尽所能向前冲!
即计算有多少对(i,j)满足1<=i<j<=n,且a[i]<=a[j]

输入
第一行输入一个整数N(1<=N<=100000)
第二行输入N个整数ai(0<=a[i]<=10^9),代表第i个徒弟的考试分数

输出
从小到大输出N个数,每相邻两个数之间有一个空格

样例输入
5
5 4 2 4 5

样例输出
6

提示
徒弟4逆袭他的师兄2,3;徒弟5逆袭他的师兄1,2,3,4

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • KingJordon console.log( ) 1年前

    逆序数 归并排序 暴力解可能会超时

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define maxn 500010
    #define ll long long int
    using namespace std;
    ll a[maxn];
    ll temp[maxn];
    ll sum;
    void Merge(int l,int r,int m)
    {
        int i=l;
        int j = m + 1;
        int k = l;
        while(i<=m&&j<=r)
        {
            if(a[i]>a[j])
            {
                sum+=m-i+1;///剩下的没有进入临时空间的元素的个数
                temp[k++]=a[j++];
            }
            else
            {
                temp[k++]=a[i++];
            }
        }
        while(i<=m)///将剩余的元素存到数组中
        {
            temp[k++]=a[i++];
        }
        while(j<=r)
        {
            temp[k++]=a[j++];
        }
        for(i=l; i<=r; i++)
        {
            a[i]=temp[i];
        }
    }
    void mergesort(int l,int r)
    {
        if(l<r)
        {
            int m = (l + r) / 2;
            mergesort(l,m);///左二分排序
            mergesort(m+1,r);///右二分排序
            Merge(l,r,m);///合并两个升序数组
        }
    }
    int main()
    {
        int n,i;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0)
            {
                break;
            }
            for(i=0; i<n; i++)
            {
                scanf("%lld",&a[i]);
            }
            sum=0;
            mergesort(0,n-1);
            printf("%lld ",n*(n-1)/2-sum);
        }
        return 0;
    }
    
    点赞 1 评论 复制链接分享