python蓝桥杯省赛冲刺篇——3真题：答疑、鲁卡斯队列、金币、最大化股票交易的利润、谈判、排座椅

注意：加了链接！！！

1. 答疑

链接：https://www.lanqiao.cn/problems/1025/learning/

题目描述

有 $n$ 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下：

1. 首先进入办公室，编号为 $i$ 的同学需要 $s_i$毫秒的时间。
2. 然后同学问问题老师解答，编号为 $i$ 的同学需要 $a_i$毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
4. 最后同学收拾东西离开办公室，需要 $e_i$毫秒的时间。一般需要 $10$ 秒、$20$ 秒或 $30$ 秒，即 $e_i$
   取值为 $10000$，$20000$ 或 $30000$。

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从 $0$ 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。

输入描述

输入第一行包含一个整数 $n$，表示同学的数量。

接下来 $n$ 行，描述每位同学的时间。其中第 $i$ 行包含三个整数 $s_i$, $a_i$, $e_i$，意义如上所述。

其中有 ，$1\le n\le 1000，1\le s_i\le 60000，1\le a_i\le 10^6，e_i\in 10000,20000,30000$即 $e_i$​一定是 $10000、20000、30000$ 之一。

输出描述

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

输入输出样例

示例

输入

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

输出

280000

详解与代码演示

这是一道典型的贪心算法的题目，要求时刻最短，我们就需要求每个人用时最短的时间，对每个人用时升序，计算每个人时刻，最后相加即可。

n = int(input())
l1 = []
for i in  range(n):
    si, ai, ei = map(int, input().split())
    l1.append([si, ai, ei])
l1 = sorted(l1, key=lambda x:sum(x))
s = 0
t0 = [0,0,0]
t0s = 0
for i in range(n):
    t1 = t0s + sum(l1[i][:2])
    s += t1
    t0s += sum(l1[i])
print(s)

2. 鲁卡斯队列

链接：https://www.lanqiao.cn/problems/736/learning/

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

黄金分割数 $0.618$ 与美学有重要的关系。舞台上报幕员所站的位置大约就是舞台宽度的 $0.618$ 处，墙上的画像一般也挂在房间高度的 $0.618$ 处，甚至股票的波动据说也能找到 $0.618$ 的影子…

黄金分割数是个无理数，也就是无法表示为两个整数的比值。$0.618$ 只是它的近似值，其真值可以通过对 $5$ 开方减去 $1$ 再除以 $2$ 来获得，我们取它的一个较精确的近似值：$0.618034$。

有趣的是，一些简单的数列中也会包含这个无理数，这很令数学家震惊！

1 3 4 7 11 18 29 47… 称为“鲁卡斯队列”。它后面的每一个项都是前边两项的和。

如果观察前后两项的比值，即：$1/3,3/4,4/7,7/11,11/18...$会发现它越来越接近于黄金分割数！

你的任务就是计算出从哪一项开始，这个比值四舍五入后已经达到了与 $0.618034$ 一致的精度。

请写出该比值。格式是：分子/分母。比如：$29/47$。

详解与代码演示

这道题是一个比较简单的动态规划的题目，我们可以设立一个初始列表，利用$l_n=l[-1]+l[-2]$对数列进行访问即可。

l = [1.0, 3.0]
while True:
    a = round(l[-2] / l[-1], 6) # 四舍五入保留6位有效小数
    if len(str(a)) >= len('0.618034'):
        if str(a)[:8] == '0.618034':
            print('{}/{}'.format(int(l[-2]),int(l[-1])))
            break
    l_n = l[-1] + l[-2]
    l.append(l_n)

3. 金币

链接：https://www.lanqiao.cn/problems/357/learning/

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币…；这种工资发放模式会一直这样延续下去：当连续 $N$ 天每天收到 $N$ 枚金币后，骑士会在之后的连续 $N+1$ 天里，每天收到 $N+1$ 枚金币。

请计算在前 $K$ 天里，骑士一共获得了多少金币。

输入描述

输入只有 1 行，包含一个正整数 $K（1\le K\le 10^4）$，表示发放金币的天数。

输出描述

输出只有 1 行，包含一个正整数，即骑士收到的金币数。

输入输出样例

示例1

输入

6

输出

14

示例2

输入

1000

输出

29820

详解与代码演示

这题有点像前缀和算法，但是我们也可以通过暴力枚举。

n = int(input())
s = 0
l = [1]
i = 2
while len(l)<=n:
    l.extend([i]*i)
    i += 1
print(sum(l[:n]))

4. 最大化股票交易的利润

链接：https://www.lanqiao.cn/problems/307/learning/

题目描述

实现一个算法寻找最大化股票交易利润的策略。介绍如下：

• 股票价格每天都在变化，以数组的索引表示交易日，以数组的元素表示每天的股票价格。
• 可以通过买入和卖出获得利润。一天只能进行一次买入或卖出操作，一次买入加卖出操作称为一次交易次数。
• 可以通过买入和卖出获得利润。一天只能进行一次买入或卖出操作，一次买入加卖出操作称为一次交易次数。

输入描述

第一行为数字 $N$，表示共有 $N$ 天。

第二行为 $N$ 个数字 $A_i$，表示每天的股票价格。

其中，$1\le N,A_i\le 10^4$。

输出描述

输出一行，为交易一次的最大利润（有可能利润为负）。

输入输出样例

示例

输入

8
2 5 6 1 4 3 1 3

输出

4

详解与代码演示

这是一道模拟题，直接暴力枚举即可。利用后面的价格逐一减去前面的价格即可。

n = int(input())
l = list(map(int, input().split()))
i = 0
max_ = l[1] - l[0]
j = n -1
while i < j:
    while i < j:
        if l[j] - l[i] >= max_:

            max_ = l[j] - l[i]
        j -= 1
    i += 1
    j = n -1
print(max_)

5. 谈判

链接：https://www.lanqiao.cn/problems/545/learning/

题目描述

在很久很久以前，有 $n$ 个部落居住在平原上，依次编号为 $1$ 到 $n$。第 $i$ 个部落的人数为 $t_i$。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

输入描述

输入的第一行包含一个整数 $n$，表示部落的数量。

第二行包含 $n$ 个正整数，依次表示每个部落的人数。

其中，$1\le n\le 1000，1\le t_i\le 10^4$。

输出描述

输出一个整数，表示最小花费。

输入输出样例

示例1

输入

4
9 1 3 5

输出

31

详解与代码解析

这是一道贪心算法的题目，要使花费最小，就需要从开始就按最小花费来计算，如上例子1+3花费4，4+5花费9，9+9花费18，一共4+9+18=31。

import os
import sys

# 请在此输入您的代码
def talk(data):
    data.sort()
    count = data[0] + data[1]
    sum1 = data[0] + data[1]
    for i in range(2, n):
        sum1 += data[i] # 融合的人数
        count += sum1 # 一共的花费
    return count

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(talk(a))

6. 排座椅

链接：https://www.lanqiao.cn/problems/524/learning/

题目描述

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 DD 对同学上课时会交头接耳。同学们在教室中坐成了 MM 行 NN 列，坐在第 $i$ 行第 $j$ 列的同学的位置是$（i，j）$，为了方便同学们进出，在教室中设置了 KK 条横向的通道，LL 条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。

输入描述

输入第一行，有 5 各用空格隔开的整数，分别是 $M，N，K，L，D（2\le N，M\le 1000，0\le K<M，0\le L<N，D\le 2000）$。

接下来 $D$ 行，每行有 4 个用空格隔开的整数，第 $i$ 行的 $4$ 个整数 $X_i，Y_i，P_i，Q_i$
，表示坐在位置 $(X_i,Y_i)$与 $(P_i,Q_i)$的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

输出描述

输出共两行。

第一行包含 $K$ 个整数，$a_1,a_2,\cdots a_K$，表示第 $a_1$行和 $a_1+1$行之间、第 $a_2$行和第 $a_2+1$行之间、…、第 $a_K$行和第 $a_K+1$行之间要开辟通道，其中 $a_i<a_i+1$，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含 $L$ 个整数，$b_1,b_2,\cdots b_k$
,表示第 $b_1$列和 $b_1+1$列之间、第 $b_2$列和第 $b_2+1$ 列之间、…、第 $b_L$列和第 $b_L+1$ 列之间要开辟通道，其中 b_i < b_i+1$，每两个整数之间用空格隔开（行尾没有空格）。

输入输出样例

示例1

输入

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

输出

2
2 4

详解与代码演示

这题是一道贪心算法的题目，要想使交头接耳的人最少，我们就可以求每行每列分割之后交头接耳最多的对数。刚好交头接耳的人要么行相同，要么列相同。所以我们可以用a列表存储m行交头接耳同学数，b列表存储n列交头接耳同学数。每次取最多即可。

# 请在此输入您的代码
m,n,k,l,d = map(int,input().split())
a=[0 for i in range(m)]   #将m行初始值设为交头接耳同学数为零
b=[0 for i in range(n)]   #将n列初始值设为交头接耳同学数为零
for i in range(d):
    x,y,p,q = map(int,input().split())
    # abs(x-p)==1 列方向上交头接耳
    if abs(x-p)==1:
        if x>p:
            a[p]+=1
        else:
            a[x]+=1
    # if abs(y-q)==1 行方向交头接耳
    if abs(y-q)==1:
        if y>q:
            b[q]+=1
        else:
            b[y]+=1

la=[]
for i in range(k):
    s=max(a) # 每行最多的交头接耳的人数
    ans=a.index(s)
    la.append(ans)
    a[ans]=0
la.sort()
for i in la:
    print(i,end=' ')
print()

lb=[]
for i in range(l):
    s=max(b)
    ans=b.index(s)
    lb.append(ans)
    b[ans]=0
lb.sort()
for i in lb[:-1]:
    print(i,end=' ')
print(lb[-1],end='')