今日复习计划：做复习题

例题1：大石头的搬运工

问题描述：

在一款名为“大石头的搬运工”的游戏中，玩家需要 操作一排n堆石头，进行n - 1轮游戏。

每一轮，玩家可以选择一堆石头，并将其移动到任意位置。

在n - 1轮游戏移动结束时，要求将所有的石头移动到一起（即所有石头的位置相同）即为成功。

移动的费用为石头的重量乘以移动的距离。例如，如果一堆重量为2的石头从位置3移动到位置5，那么费用为2 * （5 - 3） = 4.

请计算出所有合法方案中，将所有石头移动到一起时的最少费用。

可能有多堆石头在一个位置上，但是一轮只能选择移动其中一堆。

输入格式：

第一行一个整数n，表示石头的数量。

接下来n行，每行两个整数wi和pi，分别表示第i个石头的重量和初始位置。

输出格式：

输出一个整数，表示最小的总移动费用。

参考答案：

import math
n = int(input())
li = []
for i in range(n):li.append(list(map(int,input().split())))
li.sort(key = lambda x:x[1])
pre = [0]
nex = [0]
s1 = li[0][0]
s2 = li[-1][0]
for i in range(1,n):pre.append(pre[-1] + (s1)*(li[i][1] - li[i-1][1]))s1 += li[i][0]
for i in range(n-2,-1,-1):nex.append(nex[-1] + (s2)*(li[i+1][1] - li[i][1]))s2 += li[i][0]
nex.reverse()
res = math.inf
for i in range(n):res = min(res,pre[i] + nex[i])
print(res)

运行结果：

以下是我对此题的理解：

import math：

这行导入了python的math模块，用于进行数学计算。

n = int(input())

li = []

for i in range(n):li.append(list(map(int,input().split())))

首先，从标准输入读取一个整数n，表示石头的数量。然后，通过一个循环读取n行输入，每行包括两个整数wi和pi，分别表示第i个石头的重量和初始位置，这些信息以列表的形式存储在li中

li.sort(key = lambda x:x[1])

对列表li按初始位置进行排序，以便后续计算。

pre = [0]

nex = [0]

s1 = li[0][0]

s2 = li[-1][0]

初始化四个变量：pre,nex,s1,s2。pre和nex分别用于储存每个位置左侧和右侧的移动总费用，而s1和s2分别表示左侧和右侧的石头重量之和的累加值，初始值分别为第一个和最后一个石头的重量。

for i in range(1,n):pre.append(pre[-1] + (s1)*(li[i][1] - li[i-1][1]))

s1 += li[i][0]

接下来，变量列表li中的每个石头，计算每个石头左侧的移动总费用。对于每个位置i，其左侧移动总费用等于前一个位置的左侧移动总费用加上当前位置的移动费用，其中移动费用等于当前位置当前位置左侧石头重量之和乘以当前位置与前一个位置的距离。更新s1为当前位置左侧的石头重量之和。

for i in range(1,n)

这个循环从1开始到n - 1结束，遍历除了第一个石头以外的所有石头。因为第一个石头的位置是我们用来初始化s1的起点，所以不需要再次计算它的移动费用

pre.append(pre[-1] + (s1)*(li[i][1] - li[i-1][1]))

这行代码是计算并存储到当前位置i为止，所以左侧石头移动到当前位置的总费用，pre[-1]是上一个位置的移动总费用，(s1)*(li[i][1] - li[i-1][1])是从上一个位置到当前位置的移动费用，其中s1是到当前位置为止，左侧所有石头的重量和，li[i][1] - li[i-1][1]是当前位置与上一个位置的距离。将这两者相加得到当前位置的总移动费用，并将其追加到pre列表中

s1 += li[i][0]

这行代码更新了s1的值。每遍历到一个新的位置，都将当前位置的石头重量加到s1上，因此s1始终保持为到当前位置为止，左侧所有石头的重量和。

for i in range(n - 2,-1,-1)

这个循环从倒数第二个石头开始向左遍历，直到第一个石头。因为最后一个石头的位置是我们用来初始化s2的起点，所以不需要再次计算它的移动费用

nex.append(nex[-1] + (s2)*(li[i + 1][1] - li[i][1]))

这行代码是计算并储存到当前位置i为止，所有右侧石头移动到当前位置的总移动费用，nex[-1]是上一个位置的总移动费用，(s2)*(li[i + 1][1] - li[i][1])是从上一个位置移动到当前位置的移动费用，其中s2是到当前位置为止，右侧所有石头的重量和，li[i + 1][1] - li[i][1]是当前位置与下一个位置之间的距离。将这两者相加得到当前位置的总移动费用，并将其追加到nex列表中。

s2 += li[i][0]：这行代码更新了s2的值，每遍历到一个新的位置，将当前石头的重量叠加到s2上，因此s2始终保持为到当前位置为止，右侧所有石头的重量和。

nex.reverse()：最后，由于我们是从左向右计算移动费用的，得到的nex列表中元素的顺序与实际的位置顺序相反，所以需要将nex翻转过来，以便后续计算最小总移动费用是能够对应正确位置。

---

例题2：最大数组和

问题描述：

小明是一名勇敢的探险家，他在一次探险途中发现了一组神秘的宝石，这些宝石的价值都不同。但是，他发现这些宝石会随着时间的推移逐渐失去价值，因此他必须在规定的次数内对它们进行处理。

小明想要最大化这些宝石的总价值。他有两种处理方式：

1.选出最小的两个宝石，并将他们从宝石组中删除。

现在，给你小明手上的宝石组，请你告诉他在规定的次数内，最大化宝石的总价值是多少。

输入格式：

第一行包含一个整数t，表示数据组数。

对于每组数据，第一行包含两个整数n和k，表示宝石的数量和规定的处理次数。

第二行包含n个整数a1,a2,a3,...,an,表示每个宝石的价值。

输出格式：

对于每组数据，输入一个整数，表示在规定的次数内，最大化宝石的总价值。

参考答案：

import math
t = int(input())
for i in range(t):n,k = map(int,input().split())li = list(map(int,input().split()))li.sort()pex = [0]for i in range(n):pex.append(pex[-1] + li[i])ans = -math.inffor i in range(k + 1):ans = max(ans,pex[n - (k - i)] - pex[2 * i])print(ans)

运行结果：

 

以下是我对此题的理解：

1.输入

第一行输入一个整数t，表示数据组数

对于每组数据，第一行输入两个整数n和k，分别表示宝石的数量和规定的处理次数。

第二行输入n个整数，表示每个宝石的价值

2.数据处理

程序进入一个循环，循环t次，处理每组数据

对于每组数据，首先将宝石价值列表li进行排序，从小到大排序

3.计算累积和

创建一个列表pex，初始为[0]

然后，对排列后的宝石价值列表进行循环，计算累积和，并将结果存储在pex中

这样，pex中的第i个元素表示前i个宝石的总价值。

4.计算最大总价值

初始化ans为负无穷，表示初始时宝石总价值为最小值

对于处理次数k的所以可能值，从0到k，进行循环

计算当前处理次数下，剩余宝石的最大总价值

使用max函数更新ans，保留最大的总价值

5.输出结果

输出ans，即最大化宝石总价值的结果。

这道题使用了贪心算法的思想，在每次处理中选择了当前最优的方案，以求得最终的最优解。

---

OK，今天去做别的事情了，所以我只做了两个题，进度有点慢，明天得快一点。

下一篇继续！