【洛谷】P1116 车厢重组【python版】
Python 洛谷 重组
2023-09-14 09:13:20 时间
【洛谷】P1116 车厢重组【python】
0.题意
本题目写成入门的红题总感觉有些不妥,至少是普及的级别了吧。徒手写归并也不是2min就能搞定的。
1.分析
用归并排序求逆序数
本题主要有如下几个点需要注意:
01.归并排序用Python的写法
02.python 中数组如果没有申请足够大小是无法直接通过下标访问的
03.样例输入输出的问题。本题的测试样例采取了三种 不同的输入方式:
a.以空格分割
b.以换行分割
c.以空格和换行分割
反正输入的数据特别烦人,从C++转Python真的是很不习惯。
2.代码
N = 10005
res = 0
temp = [0] * N # 临时数组,必须使用这种方式才可以,如果直接用.append()的话,会出现问题
# 使用归并排序
def mergeSort(left,right):
global res
global temp
if left >= right: # 直接返回
return
mid = (left+right)//2 # 直接二分
mergeSort(left,mid)
mergeSort(mid+1,right)
# 开始合并
index = tl = left
tr = mid + 1
while tl <= mid and tr <= right:
if arr[tl] <= arr[tr]:
temp[index] = arr[tl] # 开始赋值
tl += 1
index += 1
# 如果是从右侧开始赋值,说明左侧的值要大
if arr[tr] <= arr[tl]:
temp[index] = arr[tr] # 开始赋值
tr+=1
index+=1
res += (mid - tl + 1)
# 赋值剩余的数组值
while tl<=mid:
temp[index]=arr[tl]
tl+=1
index+=1
while tr<=right:
temp[index] = arr[tr]
index+=1
tr+=1
res += (mid-tl+1)
# 写回到arr 数组中
for i in range(left,right+1):
arr[i] = temp[i]
n = input()
n = int(n)
arr=[]
while len(arr)<n: # 如果没有读够n个数字
num = input()
nums = num.strip().split()
nums = [int(i) for i in nums]
for i in nums:
arr.append(i)
#print(arr)
# 进行一个归并排序
mergeSort(0,n-1)
# for i in range(n):
# print(arr[i],end = " ")
print(res)
"""
5
1 4 2 5 3
5
1
2
3
4
5
"""
相关文章
- 【python教程入门学习】PyCharm下载和安装教程(包含配置Python解释器)
- Python 编程 | 连载 25 - Python 多进程
- python re.compile() 详解——Python正则表达式「建议收藏」
- Mac os 安装Python Pycharm 配置环境「建议收藏」
- python中sqrt函数用法_Python : sqrt() 函数
- arcpy怎么用_python arcpy
- Python编程 whl文件安装库
- 【说站】python逻辑值检测如何实现
- python读取pkl_Python 读取文件
- Python的正则表达式_python正则表达式例子
- python的特点和优势_Java与Python异同
- lambda表达式python_Python中的Lambda表达式「建议收藏」
- Python 冒泡排序_python
- python isalpha函数用法_isalpha函数「建议收藏」
- 在python中用来安装第三方库的常用工具_什么库用于安装管理Python扩展包
- python的缩进规则是什么意思_python什么情况下需要缩进
- python中if判断语句的用法_Python if判断语句的用法详细介绍[通俗易懂]
- python deepcopy函数_Python deepcopy
- python定义函数求和_Python定义函数实现累计求和操作
- 【2】VScode 搭建python和tensorflow环境
- Python列表推导式(2)_Python自学第二十四节
- Python垃圾回收机制
- python(PIL)图像处理(等比例压缩、裁剪压缩) 缩略(水印)图详解编程语言
- Python输出函数print()总结(python print())详解编程语言
- python从MSSQL到Python:一段跨语言的旅程(mssql除以)
- 从 Python 连接到 MySQL:实现更多强大的数据库应用(python和mysql)
- python删除文件示例分享
- Python编写检测数据库SA用户的方法