九度OJ 1348-数组中的逆序对【逆序对模板】

深碍√TFBOYSˉ_ 2022-07-24 10:13 158阅读 0赞

题目1348：数组中的逆序对

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：2893

解决：692

**题目描述：**

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

**输入：**

每个测试案例包括两行：

第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。

第二行包含n个整数，每个数组均为int类型。

**输出：**

对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。

**样例输入：**

4
    7 5 6 4

**样例输出：**

5

#include<stdio.h> 
    #include<cstring>
    long long cnt;
    int a[100000+100],c[100000+100];
    void merge(int a[], int first, int mid, int last, int c[])
    {
        int i = first, j = mid + 1;
        int m = mid, n = last;
        int k = 0;
        while(i <= m || j <= n)
        {
            if(j > n || (i <= m && a[i] <= a[j]))
                c[k++] = a[i++];
            else
            {
                c[k++] = a[j++];
                cnt += (m - i + 1);
            }
        }
        for(i = 0; i < k; i++)
            a[first + i] = c[i];
    }
    void merge_sort(int a[], int first, int last, int c[])
    {
        if(first < last)
        {
            int mid = (first + last) / 2;
            merge_sort(a, first, mid, c);
            merge_sort(a, mid+1, last, c);
            merge(a, first, mid, last, c);
        }
    }
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		cnt=0;
    		memset(c,0,sizeof(c));
    		merge_sort(a,0,n-1,c);
    		printf("%lld\n",cnt);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关数组中的逆序对

一、题目在数组中，如果前一个数字大于后一个数字，则两个数字组成一个逆序对。输入一个数组，求逆序对总数。二、分析（1）暴力求解：顺序扫描这个数组，每扫描到一个数字，如

超、凢脫俗/ 2023年11月20日 07:37/ 0 赞/ 247 阅读

相关 1013 逆序对

Description 给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算逆序对个数.当i<j且a[i]>a[j], 则称a[i]与a[j]是一对

墨蓝/ 2022年09月11日 15:21/ 0 赞/ 164 阅读

相关九度OJ 1348-数组中的逆序对【逆序对模板】

题目1348：数组中的逆序对时间限制：1 秒内存限制：32 兆特殊判题：否提交：2893 解决：692 题目描述：在数组中的两个数字，如果前面一个数字大

深碍√TFBOYSˉ_/ 2022年07月24日 10:13/ 0 赞/ 159 阅读

相关数组中的逆序对

![这里写图片描述][70] public class Solution { public int count=0; //方法一、暴力

系统管理员/ 2022年05月25日 10:38/ 0 赞/ 192 阅读

相关数组中的逆序对

写在前面 > 题目：剑指offer-数组中的逆序对 > 考点：归并排序。知识点归并排序要求 > 在数组中的两个数字，如果前面一个数字大于

约定不等于承诺〃/ 2022年05月18日 07:15/ 0 赞/ 169 阅读

相关数组中的逆序对 java

数组中的逆序对 java 题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将

爱被打了一巴掌/ 2022年05月15日 15:26/ 0 赞/ 201 阅读

相关数组中的逆序对

[数组中的逆序对][Link 1] 题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的

Myth丶恋晨/ 2022年03月25日 15:38/ 0 赞/ 199 阅读

相关数组中的逆序对

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=19][

àì夳堔傛蜴生んèń/ 2022年03月20日 03:27/ 0 赞/ 225 阅读

相关数组中的逆序对

时间限制：2秒空间限制：32768K 热度指数：259937 本题知识点：数组算法知识视频讲解题目描述在数组中的两个数字，如果前面一个数字大于后面的数

比眉伴天荒/ 2022年03月09日 10:50/ 0 赞/ 220 阅读

相关排序---逆序对

题目：[https://www.acwing.com/problem/content/description/109/][https_www.acwing.com_proble

喜欢ヅ旅行/ 2022年02月23日 09:34/ 0 赞/ 217 阅读