热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2022年11月2日AcWing每日编程挑战

在2022年11月2日的AcWing每日编程挑战中,任务是计算一个长度为n的整数序列中的逆序对数量。逆序对是指在序列中,若存在两个下标i和j(ia[j],则称这两个元素构成一个逆序对。本题要求实现一个算法来高效地统计这些逆序对的数量。
逆序对的个数

给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 ia[j],则其为一个逆序对;否则不是。

输入格式

第一行包含整数 n,表示数列的长度。

第二行包含 n 个整数,表示整个数列。

输出格式

输出一个整数,表示逆序对的个数。

数据范围

1≤n≤100000,

数列中的元素的取值范围 [1,109]。

输入样例:

6

2 3 4 5 6 1

输出样例:

5


个人解析:

根据题意可知这是一道求逆序对的题,我想第一次碰到这种题都是暴力求解吧,但这里我们其实也可以使用归并排序和树状数组(不会),因此我也只能先用归并排序求解一遍了。


算法实现:

主要就是归并排序,只不过多了一行代码罢了。,其主要思想在于分治和单调性。

那么我们先来看归并排序的实现:

1.先将数组从中间一分为二,形成两个子数组,然后不断递归分割下去,直到剩下一个数时停止。不断对递归过程中产生的左右两个子数组进行合并排序(这里可以使用双指针优化),记住我们是先递归再优化因此数组长度是从小到大。如当两个数组长度为2时,对其进行合并排序成一个长度为4的数组,如果数组长度不是偶数,则根据向下取整的特性选取中点。除此之外,左右两个子数组也都是单调的,毕竟是先排序再合并的。

2.在第1步使用双指针排序数组,即先创建一个temp数组作为中间数组,将左数组的一个数与右数组的一个数进行比较,谁小谁先放进temp(升序),直至某一个数组排序完成就退出排序过程,但如果另一个数组依然存在数的话,也一定是较大的,直接接到temp数组后面即可。

3.用排序后的新数组temp覆盖掉原来对应位置上的旧数组就相当于完成了对这一部分的合并排序,并将其用在后续的排序中。

需要格外注意的是,基于单调性我们可以知道当左数组存在一个数x比右数组的一个数y要大时,那么由于左数组是单调递增的,则从x往后的所有数都比y要大,因此逆序对的个数是从x开始到左子数组结束,也就是mid-i+1(i是x在左子数组中的下标)


代码实现:

#include

#include

#include

using namespace std;
void merge_sort(int q[],int l,int r,long long *ans){

if(l >= r) return ;

int tmp[100000];

int mid = (l+r) >> 1;

merge_sort(q,l,mid,ans);

merge_sort(q,mid+1,r,ans);

int i=l,j = mid+1,cnt = 0;

while(i <= mid && j <= r){

if(q[i] <= q[j]){

tmp[cnt ++] = q[i++];

}

else{

tmp[cnt ++] = q[j++];

*ans += mid - i + 1; // 分治+单调即可

}

}

while(i <= mid) tmp[cnt++] = q[i++];

while(j <= r) tmp[cnt++] = q[j++];

for(i=l,j=0; i<=r ; ++i, ++j){

q[i] = tmp[j];

}

}
int main()

{

long long ans = 0;

int a[100000] = {0};

int n;

cin >> n;

for(int i=0; i > a[i];

merge_sort(a,0,n-1,&ans);

printf("%lld",ans);

return 0;

}


2022-11-02 Acwing每日一题的相关教程结束。



推荐阅读
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 双指针法在链表问题中应用广泛,能够高效解决多种经典问题,如合并两个有序链表、合并多个有序链表、查找倒数第k个节点等。本文将详细介绍这些应用场景及其解决方案。 ... [详细]
  • Laravel 开发技巧:如何为集合中的每个元素添加递增编号
    本文将介绍如何在 Laravel 集合中为每个数组元素添加递增的编号,帮助开发者更好地管理和操作数据。 ... [详细]
  • C语言中全部可用的数学函数有哪些?2.longlabs(longn);求长整型数的绝对值。3.doublefabs(doublex);求实数的绝对值。4.doublefloor(d ... [详细]
  • String字符串与字符数组#includeStringintmain(){char*strhello;字符串与字符数组的关系:字符串是 ... [详细]
  • 字符串学习时间:1.5W(“W”周,下同)知识点checkliststrlen()函数的返回值是什么类型的?字 ... [详细]
  • [转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]
  • 字节流(InputStream和OutputStream),字节流读写文件,字节流的缓冲区,字节缓冲流
    字节流抽象类InputStream和OutputStream是字节流的顶级父类所有的字节输入流都继承自InputStream,所有的输出流都继承子OutputStreamInput ... [详细]
  • 如何在Java中使用DButils类
    这期内容当中小编将会给大家带来有关如何在Java中使用DButils类,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。D ... [详细]
  • 本文介绍了一种在ANSI C中动态分配二维数组的方法。通过创建指针数组并为每个指针分配连续空间,可以灵活地管理内存。文章还讨论了一些常见的错误和注意事项。 ... [详细]
  • 2.2 组件间父子通信机制详解
    2.2 组件间父子通信机制详解 ... [详细]
  • 在《Cocos2d-x学习笔记:基础概念解析与内存管理机制深入探讨》中,详细介绍了Cocos2d-x的基础概念,并深入分析了其内存管理机制。特别是针对Boost库引入的智能指针管理方法进行了详细的讲解,例如在处理鱼的运动过程中,可以通过编写自定义函数来动态计算角度变化,利用CallFunc回调机制实现高效的游戏逻辑控制。此外,文章还探讨了如何通过智能指针优化资源管理和避免内存泄漏,为开发者提供了实用的编程技巧和最佳实践。 ... [详细]
  • 深入解析:Synchronized 关键字在 Java 中对 int 和 Integer 对象的作用与影响
    深入探讨了 `Synchronized` 关键字在 Java 中对 `int` 和 `Integer` 对象的影响。尽管初看此题似乎简单,但其实质在于理解对象的概念。根据《Java编程思想》第二章的观点,一切皆为对象。本文详细分析了 `Synchronized` 关键字在不同数据类型上的作用机制,特别是对基本数据类型 `int` 和包装类 `Integer` 的区别处理,帮助读者深入理解 Java 中的同步机制及其在多线程环境中的应用。 ... [详细]
  • 深入解析 Synchronized 锁的升级机制及其在并发编程中的应用
    深入解析 Synchronized 锁的升级机制及其在并发编程中的应用 ... [详细]
  • 遗传算法中选择算子为何置于交叉算子和变异算子之前?本文探讨了这一问题,并详细介绍了遗传算法中常用的选择算子类型及其作用机制。此外,还分析了不同选择算子对算法性能的影响,为实际应用提供了理论依据。 ... [详细]
author-avatar
tomodachitch
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有