今日复习内容:做题
例题1:蓝桥骑士
问题描述:
小蓝是蓝桥王国的骑士,他喜欢不断突破自我。
这天蓝桥国王给他安排了N个对手,他们的战力值分别为a1,a2,...,an,且按顺序阻挡在小蓝的前方。对于这些对手小蓝可以选择挑战,也可以选择避战。
身为高傲的骑士,小蓝从不走回头路,且只愿意挑战战力值越来越高的对手。
请你算算小蓝最多会挑战多少名对手?
输入描述:
输入第一行包括一个整数N,表示对手的个数;
第二行包括N个整数:a1,a2,...an,表示每个骑士的战力值;
1 <= N <= 3*10^5,1 <= ai <= 10^9。
输出描述:
输出一行整数表示答案。
参考答案:
import bisect
n = int(input())
a = list(map(int,input().split()))
q = [a[0]]
for i in range(1,n):
ind = bisect.bisect_left(q,a[i])
if ind == len(q):
q.append(a[i])
else:
q[ind] = a[i]
print(len(q))
运行结果:
以下是我对此题的理解:
首先,从输入中获取对手的个数和每个对手的战力值;
创建一个空列表q,用于存储已经被挑战过的对手的战力值;
从第一个对手开始,遍历到最后一个对手,依次进行以下操作:
使用二分查找在列表q中找到小于等于当前对手战力值的最大值的索引;
如果找到的索引等于q的长度,说明当前对手的战力值大于当前已经挑战过的所有对手的战力值,将当前对手的战力值加入q中,否则,说明当前对手的战力值可以替换q中某个已经挑战过的对手的战力值,最后输出q的长度就可以了。
例题2:最长公共子序列
问题描述:
给定一个长度为N的数组a和一个长度为M的数组b,请你求出它们的最长公共子序列。
输入描述:
输入第一行包括两个整数N和M,分别表示数组a的长度和数组b的长度。
第二行输入包含N个整数a1,a2,...,an;
第三行包含M个整数b1,b2,...bm;
1 <= N,M <= 10^3,1 <= ai,bi <= 10^9
输出描述:
输出一行整数表示答案
参考答案:
a,b = map(int,input().split())
A = [0] + list(map(int,input().split()))
B = [0] + list(map(int,input().split()))
f = [[0]*(b + 1)for i in range(a + 1)]
for i in range(1,a + 1):
for j in range(1,b + 1):
if A[i] == B[j]:
f[i][j] = f[i-1][j-1] + 1
else:
f[i][j] = max(f[i-1][j],f[i][j-1])
print(f[a][b])
运行结果:
这道题用的是动态规划,比较简单,我就不做过多解释了。
例题3:倒水
问题描述:
小秋家里来了n位客人,编号为1,2,...,n,现在小秋要给每个客人倒水。
每个客人都有一个满意度,对于第i个客人,满意度是这样定义的:
如果小秋给第i个客人倒了ai毫升水,客人的满意度为bi;如果小秋给第i个客人倒了ci(ci > ai)毫升水,客人的满意度为di;
如果小秋给第i为客人倒的水不足ai毫升(也可以为0),客人的满意度为ei。
现在小秋有m毫升水,请问他要怎么倒水,才能让所有客人的满意度之和最大呢?你只需要求出所有客人的满意度之和的最大值。
输入描述:
第一行输入两个正整数n和m,表示客人的数量和小秋所拥有的水的体积;
接下来n行,每行5个整数ai,bi,ci,di,ei,第i行表示给第i位客人倒了ai毫升水的满意度为bi,给第i位客人倒了ci毫升水的满意度为di,倒水不足ai毫升水的满意度为ei。
输出格式:
输出仅一行,包含一个整数,表示所有课满意度之和的最大值。
参考答案:
import os
import sys
n,m = map(int,input().split())
f = [[0]*(m + 1) for i in range(n + 1)]
for i in range(1,n + 1):
a,b,c,d,e = map(int,input().split())
for j in range(m + 1):
f[i][j] = f[i - 1][j] + e
if j >= a:
f[i][j] = max(f[i][j],f[i - 1][j - a] + b)
if j >= c:
f[i][j] = max(f[i][j],f[i - 1][j - c] + d)
print(f[n][m])
运行结果:
以下是我对此题的理解:
我就不写成文字了,我把注释过的代码粘贴过来:
import os
import sys
# 输入客人数量n和水的体积m
n, m = map(int, input().split())
# 初始化动态规划数组f,f[i][j]表示考虑前i个客人,倒水体积为j时的最大满意度之和
f = [[0] * (m + 1) for i in range(n + 1)]
# 遍历每位客人
for i in range(1, n + 1):
# 获取当前客人的倒水参数
a, b, c, d, e = map(int, input().split())
# 遍历可能的倒水体积
for j in range(m + 1):
# 初始化当前状态为上一个状态加上当前客人倒水不足ai毫升时的满意度ei
f[i][j] = f[i - 1][j] + e
# 如果当前剩余水量j大于等于ai,即可以倒ai毫升水给当前客人
if j >= a:
# 尝试用当前水量j减去ai毫升水,然后加上当前客人倒水ai毫升时的满意度bi,与之前状态f[i-1][j-ai]相比较,取最大值
f[i][j] = max(f[i][j], f[i - 1][j - a] + b)
# 如果当前剩余水量j大于等于ci,即可以倒ci毫升水给当前客人
if j >= c:
# 尝试用当前水量j减去ci毫升水,然后加上当前客人倒水ci毫升时的满意度di,与之前状态f[i-1][j-ci]相比较,取最大值
f[i][j] = max(f[i][j], f[i - 1][j - c] + d)
# 输出考虑了所有客人和水量为m时的最大满意度之和
print(f[n][m])
例题4:盗墓分赃2
问题描述:
在一个探险者的团队中,小明和小红是合伙的盗墓贼。
他们成功盗取了一座古墓中的宝藏,其中包括n件不同重量的宝贵文物和黄金,第i件宝藏的重量为ai。
现在,他们希望公平地分配这些宝藏,使得小明所分得的宝藏的总重量等于小红所分得的宝藏的总重量。
请检查是否存在这样的分配方案,需要注意的是,不能对宝藏进行切割来平分重量,只能整个宝藏进行分配。
输入格式:
第一行包含一个正整数n,表示有n件宝藏;
接下来n行,第i行表示第i件宝藏的重量ai。
输出格式:
如果能公平分配就输出yes,否则输出no。
参考答案:
def work():
n = int(input())
aa = [0] + [int(input())for i in range(n)]
tot = sum(aa)
if tot % 2 != 0:
print('no')
return
tot //= 2
f = [[False]*(tot + 1) for i in range(n + 1)]
f[0][0] = True
for i in range(1,n + 1):
for j in range(tot + 1):
f[i][j] = f[i - 1][j]
if j >= aa[i]:
f[i][j] = f[i - 1][j - aa[i]]
print('yes')if f[n][tot] else print('no')
if __name__ == '__main__':
work()
运行结果:
第一种做法有一个样例显示超时了,所以我优化了一下。
第二种做法:
def work():
n = int(input())
aa = [0] + [int(input())for i in range(n)]
tot = sum(aa)
if tot % 2 != 0:
print('no')
return
tot //= 2
f = [False]*(tot + 1)
f[0] = True
for i in range(1,n + 1):
for j in range(tot,aa[i] - 1,-1):
f[j] = f[j - aa[i]]
print('yes')if f[tot] else print('no')
if __name__ == '__main__':
work()
以下是我对此题的理解:
我用代码注释来表达我的思想:
def work():
# 输入宝藏的数量n
n = int(input())
# 获取每件宝藏的重量并存储在列表aa中
aa = [0] + [int(input()) for i in range(n)]
# 计算所有宝藏的总重量
tot = sum(aa)
# 如果总重量为奇数,则无法公平分配,输出'no'并返回
if tot % 2 != 0:
print('no')
return
# 将总重量除以2,得到每个人应分得的宝藏的总重量
tot //= 2
# 创建一个布尔型数组f,f[i]表示是否存在一种方案使得宝藏的总重量为i
f = [False] * (tot + 1)
# 初始化f[0]为True,表示当没有宝藏时,总重量为0
f[0] = True
# 遍历每件宝藏
for i in range(1, n + 1):
# 从总重量到当前宝藏重量之间的位置开始遍历
for j in range(tot, aa[i] - 1, -1):
# 如果存在一种分配方案使得总重量为j的话,那么也一定存在一种分配方案使得总重量为j + 宝藏重量
f[j] = f[j - aa[i]]
# 判断是否存在一种分配方案使得总重量为tot,如果存在,则输出'yes',否则输出'no'
print('yes') if f[tot] else print('no')
if __name__ == '__main__':
work()
OK,今天状态不错,这几个题还好,下一篇继续!