蓝桥杯刷题--python-19--归并排序,离散化,hash,逆序数

2024-03-09 11:04

本文主要是介绍蓝桥杯刷题--python-19--归并排序,离散化,hash,逆序数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

505. 火柴排队 - AcWing题库

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
mod=99999997
# map
c=[0 for i in range (n+1)]
# 归并排序模板

def _MergeSort(arr,l,r,tmp):
    if  l>=r: return 0
    # 分治思想
    mid=l+r>>1
#     当前层操作
    res=(_MergeSort(arr,l,mid,tmp))+(_MergeSort(arr,mid+1,r,tmp))%mod
#     当前层逻辑
    begin1=l
    end1=mid
    begin2=mid+1
    end2=r
    index=l

    while(begin1<=end1 and begin2<=end2):
        if arr[begin1]<arr[begin2]:
            tmp[index]=arr[begin1]
            index+=1
            begin1+=1
        else:
            tmp[index]=arr[begin2]
            index+=1
            begin2+=1
            res=(res+end1-begin1+1) % mod

#    把多余的添加到数组
    # 把多余的添加到数组
    while begin1 <= end1:
        tmp[index] = arr[begin1]
        index += 1
        begin1 += 1
    while begin2 <= end2:
        tmp[index] = arr[begin2]
        index += 1
        begin2 += 1

    for i in range (l,r+1):
        arr[i]=tmp[i]
    return res

def MergeSort(arr):
    tmp=[0 for _ in range (len(arr))]
    # 调用子函数
    res=_MergeSort(arr,0,len(arr)-1,tmp)
    return res


# 离散化
def work(a):
    n=len(a)
    p= [i for i in range (1,n+1)]
    p.sort(key=lambda x:a[x-1])
    for i in range (1,n+1):
        a[p[i-1]-1]=i

work(a)
work(b)
# hash map
for i in range(n):
    c[a[i]]=i
for i in range (n):
    b[i]=c[b[i]]
print(MergeSort(b))

这篇关于蓝桥杯刷题--python-19--归并排序,离散化,hash,逆序数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/790487

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss