【CODEMATE】最小值 粤港澳信息学创新大赛 Python赛项 小学组、初中组CMP0001：最小值/高中组/体验题库CMEP46：最小值/编程题：P03886/列表排序/排序算法

前言

  想要了解粤港澳信息学创新大赛信息、有什么项目可以报名的可以查看上一篇博客：【CODEMATE】比较 粤港澳信息学创新大赛 Python赛项 初中组CMP0008：比较/高中组/体验题库CMEP45：比较/编号P03850/任意进制数之间比较/任意进制转换

---

  
  

问题描述

知识点：排序-排序概念/选择排序/插入排序/冒泡排序 体验题库 Python体验  难度值：4  尝试： 35  AC：1  上传者

  题目描述

  小明最近在学习数学问题，他遇到了一个有趣的问题。现在小明在纸上写了 2n 个数 a₁,a₂,a₃,…,a_2n。他希望将这些数两两一组划分，计算组内元素的差的绝对值再求和，使得和最小，即他希望将这些数填入下面这个式子中的未知数中，使得下面这个式子运算结果尽可能小。

  |x₂-x₁| + |x₄-x₃| + |x₆-x₅| + … + |x_2n-x_2n-1|

  请你帮助小明解决这个问题。

  输入格式

  第一行包含一个整数 n
  第二行包含 2n 个整数，表示数的值。每两个数之间用空格分隔。

  输出格式

  输出一个整数，表示表达式的最小值。

  Samples
  输入数据 1

2
1 3 2 4
1
2

  输出数据 1

2
1

  样例解释 1

  |1-2|+|3-4|=2,此时值最小

  数据范围与提示

  n ≤ 10³ , 0 ≤ a_i ≤ 10⁹

---

  
  

做题思路、解决过程

输入、输出的代码思路

  通过读题可以得知：

  本程序至少有 3 个变量：n（决定列表长度）、li（用列表存放 2n 个整数）、min（表达式最小值）

  1.输入部分分为两行，第一行接受一个参数 n，第二行接收一个长度为 2n 的列表。

  2.输出部分为一个整数 min，计算 2n 个数两两相减后相加的最小值。

  确定了以上两点，写代码时就要按着输入输出这两点要求去写。

  首先，第 1 点（输入）的第一行：定义一个变量 n ，n 的值从键盘获取：

n = int(input())
1

  然后，第1点（输入）的第二行：创建一个长度为 2n 的列表，再从键盘把 2n 个整数赋值给列表。

  按照以前用 C语言面向过程的思路去写的话是根据 n 的值创建一个长度为 2n 的数组 再去设计 scanf() 的输入格式。在 python 面向对象思想里我是这样设计的：li = [input().split() for _ in range(2*n)]，这样设计产生了什么问题呢？就是列表 li 的长度虽然是 2n，但是需要重复输入 4 行 input().split() 数据，按照输入数据1样式输入，最终列表 li 就变成这样：（列表 li 每个元素都是一个列表）。把 range(2*n) 改成 range（1） 就没问题，但是这样就和整数 n 就没有关系了同时 li 变成“二维列表”、而且这样写和 li = input().split() 的区别只有“二维列表” 和 “一维列表” 的区别。

  那为什么会出现这种情况呢，在百度“python input()底层代码的时候” 我找到了这样一句话：input() 是 Python 中的一个内置函数，用于获取用户的输入。在底层，input() 函数会从标准输入流（通常是键盘）读取一行文本，并去掉结尾的换行符（\n），然后返回该字符串。这句话说明 input() 是以换行符结束的，说明在不手动添加换行符的情况下，一行内无论输入什么那都只会被视为 “一个对象”，所以才会出现 “二维列表”； 或者由于 C语言有独特的地址符 & 结合标志符 % 所以可以在 scanf() 时准确把数值传递给每个参数。再次对 “面向过程” 和 “面向对象” 有不一样的认识。

  回到正题，第1点的第二行 新建一个长度为 2n 的列表，我选择这样设计代码（由于评分时输入必定是 2n 个整数，所以才不会出错，至于如何将一行空格分隔的整数按空格分隔将整数赋值给列表，还请各位大神多多指教）：

li = input().split()
1

  

算法部分：两两分组且差值最小值，所有分组差值相加结果最小

  首先注意到输入的 2n 个数据都是整数，那么这个数列的图像就会和函数 y = x (x∈Z) 图像重合。

  当两个数据相等时，差值最小，最小值为 0 （如1-1=0、20-20=0），换一句话说两个数间隔越小差值越小。那怎么样使得一个无序的数列两两之间的数间隔最小呢？通过图像我们可以发现，距离越近的两个点，他们之间的差值（y2-y1）才会越小，这启发我们将输入的数据排序，把对应数值的点放在对应的位置上（在图像上是 x值 和 y值，在python里就是列表下标和值），这样相邻的两个数之间差值最小。

  既然说道排序算法，想深入了解选择排序、冒泡排序、插入排序的话可以查看我这篇博客：C语言 数组的查找和排序方法 1.顺序查找 2.二分查找； 1.（简单）选择排序法 2.冒泡排序法 3.（直接）插入排序法

  python 里排序只需要用到 sort() 函数，具体用法可以查看这篇博客：Python 列表 sort()函数使用详解

  我们把输入数据从大到小排序，然后从头开始以 2 为间隔，用大的数减小的数（这样就不用加绝对值）得到差值，再把所有差值相加。至此，核心算法部分设计完成，请看代码：

# li = [int(item) for item in li]	# 将列表元素转换成 int 类型变量
li = list(map(int,li))	# 同上，第二种转换列表数据类型的方法
li.sort(reverse=True)	# reverse=True，降序排序
min=0	# 差值之和
for i in range(0, len(li)-1, 2):	# 列表内元素两两相减得到差值
    min += li[i]-li[i+1]	# 差值相加
print(min)	#输出差值的最小值
1
2
3
4
5
6
7

---

  
  

完整代码

n = int(input())
li = input().split()
# li = [int(item) for item in li]
li = list(map(int,li))
li.sort(reverse=True)
min=0
for i in range(0, len(li)-1, 2):
    min += li[i]-li[i+1]
print(min)
1
2
3
4
5
6
7
8
9

---

  
  

评测结果

---

  
  

后记

  如果您觉得代码还有改进优化的地方，请您大方点评 我虚心请教

  通过本题对 input().split() 和 列表 list 的用法有更深的理解，虽然没有手撕排序方法，自己还是回顾了之前写的排序算法的博客 温故而知新。

  坚持坚持坚持，所有的努力都会在未来变成自己闪闪发光亮点。