CSDN周赛第30期,我应试成绩“0”分。试着对天然气定单、小艺读书、买苹果🍎、圆桌四个题目,完成算法解析。
-
Python 官网:https://www.python.org/
-
Free:大咖免费“圣经”教程《 python 完全自学教程》,不仅仅是基础那么简单……
地址:https://lqpybook.readthedocs.io/
自学并不是什么神秘的东西,一个人一辈子自学的时间总是比在学校学习的时间长,没有老师的时候总是比有老师的时候多。
—— 华罗庚
- My CSDN主页、My HOT博、My Python 学习个人备忘录
- 好文力荐、 老齐教室
本文质量分:
CSDN质量分查询入口:http://www.csdn.net/qc
- ◆我的零分周赛
- 1、天然气订单
- 1.1 题目描述
- 1.2 应考代码
- 1.3 优化代码
- 1.3.1 算法优化
- 1.3.2 输出代码优化
- 2、小艺读书
- 2.1 题目描述
- 2.2 应考代码
- 2.3 优化代码
- 2.3.1 获取下标算法欠妥
- 2.3.2 优化多余语句
- 2.3.3 题目暗藏玄机
- 3、买苹果
- 3.1 题目描述
- 3.2 应考代码
- 3.3 优化代码
- 4、圆桌
- 4.1 题目描述
- 4.2 应考代码
- 5、本篇完整源码
◆我的零分周赛
CSDN第30期周赛,四个题目看起来都不难,算法感觉都会,费劲的一道道题目作答,写出来的Python3代码却是没有一题通关。😭😭
这即是“基础不牢,地动山摇”,“不写都晓得,一写啥也不明白”的真实写照啊。
偷偷录下四个题目,试着解答,以饷“伪卷”之心意;作此笔记,以警奋进……
1、天然气订单
题目 1/4 (25 分)
题目名称:天然气订单
时间限制:1000ms内存限制:256M
1.1 题目描述
天然气运输成本昂贵,危险性高,为了节省运输成本,提倡绿色环保,需要尽可能的优化订单配送,比如相同地区的天然气订单可以一次性配送。 现需要向多个地区运输天然气。但是同一个地区可能有多个订单需求。当前仅只知道某些成对的订单是同一个地区的,同一个地区的天然气需要尽可能一次性配送从而降低运输成本,所以需要尽可能的将同一个地区的订单放在一起。订单的编号是1到n。
输入描述:
输入第一行是两个正整数n,m,表示订单的数量和已知的关系数量。(1<=n,m<=10000) 接下来有m行,每行两个正整数a和b,表示a号订单和b号订单属于同一个地区(1<=a,b<=n);
输出描述:
输出第一行包含一个整数x,表示这些订单共来自x个不同的地区。接下来的输出包含x行,每行表示输出若干个订单编号,表示这些订单属于同一个地区,按照订单编号升序输出。优先输出最小的订单编号较小的地区
示例
输入
7 6
1 2
2 2
3 2
4 5
5 4
6 7
输出
3
1 2 3
4 5
6 7
提示
无
1.2 应考代码
应考答题截屏图
我参赛时的代码,虽然成功运行了但却没有通过全部测试用例。经过查验推敲,才发现算法逻辑“没问题”,但代码有“问题”。
代码逻辑:输入字符后面的六行每行前一个整数表示定单号,后一个表示定单区域(理清代码,得到输出后,才发现曲“解”题意了),用字典收集、统计定单区域,相同区域定单放一起。输出统计的区域总数及各区域定单详情。
def solution(self, n, m, vector):result = None# TODO: 请在此编写代码place = {}for i in range(m):tem = vector[i]lis = place.get(tem[1], [])lis.append(tem[0])place[tem[1]] = lis#print(place) 调试用语句。result = [str(len(place))]lis = list(place.keys())lis.sort()for i in lis:result.append(' '.join(map(str, place.get(i))))#input(result) 调试用语句。return result
代码运行效果截图
这?!😣
与“示例”输出有异啊?!回看“题目描述”,“输入第一行是两个正整数n,m,表示订单的数量和已知的关系数量”、“接下来有m行,每行两个正整数a和b,表示a号订单和b号订单属于同一个地区”,a、b是相同地域的定单号,后六行是已知定单地域的“关系数组”。
修正后的算法逻辑:遍历所有定单关系数组,把有相同定单号的关系数组中的定单号,归并在一块儿。最后输出“块儿”总数及每个“块儿”详情(每个一行)。
代码实现,取出第一组关系数组,放入result列表,遍历vector与之比对,有相同地域定单,追加入当前关系数组,无则将当前关系数组append到result列表;依次遍历,完成所有比对,sum(result )获取统计“定单区域捆绑”总数;按输出格式要求输出区域总数及详情。
def solution(self, n, m, vector):result = None# TODO: 请在此编写代码result = [vector.pop(0)] # 取出第一组关系数据放入结果列表。for i in vector: # 遍历剩下的关系数据组。#print('out:', result) # 调试用语句。a, b = iflag = Truefor j in result: # 比对并收集相同地域定单。if a in j or b in j:j.extend(i)flag = Falsebreakif flag:result.append(i) # 结果列表无相同地域,则追加。result = list(map(set, result)) # 集合去除重复收集的相同定单号。result = [' '.join(map(str, i)) for i in result] # 字符化转存输出数据。result = [str(len(result))] + result # 插入输出定单区域总数。#input(result) # 调试用语句。return result
理正题意,修改算法,。得出了正确输出。
(代码运行效果截屏)
1.3 优化代码
1.3.1 算法优化
将“比对统计”工作,封装成函数place,比设置flag开关,解题思路更明晰,代码更易于理解。
def solution(self, n, m, vector):result = None# TODO: 请在此编写代码def place(a, b):''' 收集相同地区定单 '''for i in result:if a in i or b in i:if a not in i:i.append(a)elif b not in i:i.append(b)returnreturn Trueresult = []for i in vector:''' 遍历地区关系列表 '''a, b = iif place(a, b):result.append(i)result = [' '.join(map(str, i)) for i in result]#input(result) # 调试用语句。return [str(len(result))] + result
1.3.2 输出代码优化
第一行和后六行,都可以用一行代码来写。
arr_temp = [int(item) for item in input().strip().split()]n = int(arr_temp[0])m = int(arr_temp[1])vector = []for i in range(m):vector.append([int(item) for item in input().strip().split()])
第一行,用map()函数接收键盘录入,直接为n、m赋值;后六行用列表解析+map()函数接收键盘录入并转换str-int。
n, m = map(int, input().strip().split())#input([n, m]) # 调试用语句。vector = [list(map(int, (input().strip().split()))) for i in range(m)]
2、小艺读书
题目 2/4 (25 分)
题目名称:小艺读书
时间限制:1000ms内存限制:256M
2.1 题目描述
书是人类进步的阶梯。
小艺每周因为工作的原因会选择性的每天多读几页或者少读几页。
小艺想知道一本n页的书她会在周几读完。
输入描述:
第一行输入n(1<=n<=1000);
第二行输入7个整数,分别表示周一~周日的读书页数p(0<=p<=1000)。(不考虑7个整数都为0的情况)
输出描述:
输出答案。(1-7)
示例
输入
100
15 20 20 15 10 30 45
输出
6
提示
无
2.2 应考代码
应考答题截屏图
参赛答题代码,按算法逻辑“遍历累加每计划看书页数,等于或者超过书页数n,书即看完。输出此时列表的下标+1,即是周几”,写出代码:
def solution(self, n, pages):result = None# TODO: 请在此编写代码for num in pages:n -= numif n <= 0:result = num+1print(result)breakreturn result
输出的却是31!!🤔
仔细观察,该输出下标+1,却输出了“元素+1”😂
if n <= 0:result = num+1print(result)break
所以,输出不对😂😂
修改错误代码行
if n <= 0:result = pages.index(num)+1#print(result) #调试用语句。break
得到了正确输出
2.3 优化代码
2.3.1 获取下标算法欠妥
list.index(x)函数是返回list中第一个“x”元素的下标,如果处理列表中有相同元素,就仅返回第一次出现位置的下标。打印出每次遍历的下标,就可以清楚的看到,两个“20”、两个“15”的下标,是一样的。😂这会导致,在改变要读书的页数,可能不会得到“正确”输出。
# list.index()法def solution(self, n, pages):result = None# TODO: 请在此编写代码for num in pages:print(f"\n星期{pages.index(num)+1},计划看{num}页")n -= numif n <= 0:result = pages.index(num)+1#print(result) #调试用语句。breakreturn result
可以用设置计数器或者枚举函数enmerate()同时遍历下标及元素,来修正这样子这个“bug”。
计数器设置
# 加计数器法def solution(self, n, pages):result = None# TODO: 请在此编写代码k = 0 # 计数器初始化。for num in pages:k += 1#print(f"\n星期{k},计划看{num}页")n -= numif n <= 0:result = k#print(result) #调试用语句。breakreturn result
enmerate()枚举函数遍历
# enumerate()枚举函数法def solution5(self, n, pages):result = None# TODO: 请在此编写代码for index,num in enumerate(pages):#print(f"\n星期{index+1},计划看{num}页")n -= numif n <= 0:result = index+1#print(result) #调试用语句。breakreturn result
2.3.2 优化多余语句
# 代码优化def solution3(self, n, pages):result = None# TODO: 请在此编写代码for index,num in enumerate(pages):#print(f"\n星期{index+1},计划看{num}页")n -= numif n <= 0:return index+1
当达成“看完”书的条件,豆可以直接return index+1了,不用退出循环再return 。
2.3.3 题目暗藏玄机
看过大佬的赛题解析,才明白:
-
题目没说明是周日还是周一是每周的“第一天”
我们一般都是用周一作为每周“第一”,解题依此默认。 -
书本太厚,一周读不完
遇到这种情况的输入,我的代码就只会输出默认的None了。🤪所以,在接收键盘输入后,立马来一条带“%”的代码语句,对书总页数用周计划阅读页数取余。
n = n % sum(pages) # 书总页数对一周计划阅读总量取模。
3、买苹果
题目 3/4 (25 分)
题目名称:买苹果
时间限制:1000ms内存限制:256M
3.1 题目描述
小易去附近的商店买苹果,奸诈的商贩使用了捆绑交易,只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果,小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果,小易将不会购买。
输入描述:
输入一个整数n,表示小易想购买n(1 ≤ n ≤ 100)个苹果
输出描述:
输出一个整数表示最少需要购买的袋数,如果不能买恰好n个苹果则输出-1
示例
输入
20
输出
3
提示
无
3.2 应考代码
应考答题截屏图
def solution(self, n):result = None# TODO: 请在此编写代码for i in range(n//8+1):if (n-i*8)%6 == 0:b = (n-i*8)//6print(f"\n{i}×8={i*8},{b}×6={b*6}\n")return i+breturn -1
看似得到了正解,其实不然。当把输入换过,就不一定是正解了。这说明,代码承载的算法是偏颇的,是不正解的。这是由于我对Python代码实现算法的不“能”造成的。
这道题目其实算法挺简单的,穷举所有购买方案,从中找出最少购买包数就好。
经过多翻调试,终于捋清代码逻辑😄
class Solution:def __init__(self) -> None:passdef solution(self, n):result = None# TODO: 请在此编写代码def work(result = n): # 令购买袋数初值为n。''' 穷举所有方案,遴选最少袋数 '''k = 0 # 方案数初值。for i in range(n//8+1): # 用8个一袋遍历,循环次数略少。if (n-i*8)%6 == 0:k += 1 # 方案计数。b = (n-i*8)//6if result > b+i:result = b+iprint(f"\n{k}. {i}+{b}={i+b} (8×{i}={i*8},6×{b}×6={b*6})")return resultresult = work()if result == n:return -1else:return resultif __name__ == "__main__":n = int(input('\n输入购买苹果个数:').strip())sol = Solution()print(f"{'':~^50}\n所有购买组合方案:")result = sol.solution(n)print(f"\n{'':~^50}\n输出购买总袋数:{result}")
示例截屏图
通过多个输入数据验证,无疑代码对算法的解读是正确的。我打印出了每个购买方案的详情,已经算是“一目了然”,豆不用我画蛇添足的再解说了。🤪
3.3 优化代码
以我当前水准,这花时间捋顺的代码,已“算”最优,我不能再优化的了。
4、圆桌
题目 4/4 (25 分)
题目名称:圆桌
时间限制:1000ms内存限制:256M
4.1 题目描述
有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边,但是每位客人希望自己左右边上分别有一些空座位,不然会觉得害羞。注意,如果一个客人所在的圆桌只有他一个人,那么他左边的空座位数量就是他右边的空座位数量。 试问主人需要准备多少个座位,才能让每个客人舒适的坐下。
输入描述:
第一行输入一个整数N,(1<=N<=10000),代表客人的数量 接下来N行,每行两个整数li与ri,(1<=i<=N,1<=li<=ri<=1000000000) 代表第i位客人希望左边有li个空座位,右边有ri个空座位。
输出描述:
输出一个整数,代表主人需要准备的最少座位数量。
示例1
输入
3
1 1
1 1
1 1
输出
6
示例2
输入
4
1 2
2 1
3 5
5 3
输出
15
提示
【样例解释】3个人围成一桌,每人左右各一个空位置,一共3个空座位。一个共需要3+3=6座位。
4.2 应考代码
应考答题截屏图
应试时,连题目都没有理清,所以写出了“不知所云”的代码。
“注意,如果一个客人所在的圆桌只有他一个人,那么他左边的空座位数量就是他右边的空座位数量。”题目描述中的这句话就是说,任何空座需求的客人,都可以可以单独坐一桌的,因为其左右空座会连在一起,不会违背“他左边的空座位数量就是他右边的空座位数量”。但如不拼桌则会算多空座,如示例2,分4桌坐,就应该是3 3 6 6,共需18把椅子。
我觉得,这个题目,还是另起一篇学习笔记讲述解析解题算法,要好一些。
- 圆桌 (CSDN周赛第30期第四小题,算法解析)
请点击蓝色文字跳转翻阅
5、本篇完整源码
(源码较长,点此跳过源码)
#!/sur/bin/nve python
# coding: utf-8''' CSDN周赛第30期 '''# 01 天然气定单class Solution:def __init__(self) -> None:passdef solution(self, n, m, vector):result = None# TODO: 请在此编写代码place = {}for i in range(m):tem = vector[i]lis = place.get(tem[1], [])lis.append(tem[0])place[tem[1]] = lis#print(place) 调试用语句。result = [str(len(place))]lis = list(place.keys())lis.sort()for i in lis:result.append(' '.join(map(str, place.get(i))))#input(result) 调试用语句。return resultdef solution(self, n, m, vector):result = None# TODO: 请在此编写代码result = [vector.pop(0)] # 取出第一组关系数据放入结果列表。for i in vector: # 遍历剩下的关系数据组。#print('out:', result) # 调试用语句。a, b = iflag = Truefor j in result: # 比对并收集相同地域定单。if a in j or b in j:j.extend(i)flag = Falsebreakif flag:result.append(i) # 结果列表无相同地域,则追加。result = list(map(set, result)) # 集合去除重复收集的相同定单号。result = [' '.join(map(str, i)) for i in result] # 字符化转存输出数据。result = [str(len(result))] + result # 插入输出定单区域总数。#input(result) # 调试用语句。return resultdef solution8(self, n, m, vector):result = None# TODO: 请在此编写代码def place(a, b):''' 收集相同地区定单 '''for i in result:if a in i or b in i:if a not in i:i.append(a)elif b not in i:i.append(b)returnreturn Trueresult = []for i in vector:''' 遍历地区关系列表 '''a, b = iif place(a, b):result.append(i)result = [' '.join(map(str, i)) for i in result]#input(result) # 调试用语句。return [str(len(result))] + resultif __name__ == "__main__":print('\n输入:')'''改写这段代码,让提示输入“更友好”。arr_temp = [int(item) for item in input().strip().split()]n = int(arr_temp[0])m = int(arr_temp[1])vector = []for i in range(m):vector.append([int(item) for item in input().strip().split()])'''n, m = map(int, input().strip().split())#input([n, m]) # 调试用语句。vector = [list(map(int, (input().strip().split()))) for i in range(m)]#n, m, vector = 7, 6, [[1, 2], [2, 2], [3, 2], [4, 5], [5, 4], [6, 7]] # 调试用语句。#input(f"{n}, {m}, {vector}") # 调试用语句。sol = Solution()result = sol.solution(n, m, vector)print('\n输出:') print("\n".join(result))input() # 02 小艺读书class Solution:def __init__(self) -> None:passdef solution(self, n, pages):result = None# TODO: 请在此编写代码for num in pages:n -= numif n <= 0:result = num+1print(result)breakreturn result# list.index()法def solution(self, n, pages):result = None# TODO: 请在此编写代码for num in pages:print(f"\n星期{pages.index(num)+1},计划看{num}页")n -= numif n <= 0:result = pages.index(num)+1#print(result) #调试用语句。breakreturn result# 加计数器法def solution(self, n, pages):result = None# TODO: 请在此编写代码k = 0 # 计数器初始化。for num in pages:k += 1print(f"\n星期{k},计划看{num}页")n -= numif n <= 0:result = k#print(result) #调试用语句。breakreturn result# enumerate()枚举函数法def solution5(self, n, pages):result = None# TODO: 请在此编写代码for index,num in enumerate(pages):#print(f"\n星期{index+1},计划看{num}页")n -= numif n <= 0:result = index+1#print(result) #调试用语句。breakreturn result# 代码优化def solution(self, n, pages):result = None# TODO: 请在此编写代码for index,num in enumerate(pages):#print(f"\n星期{index+1},计划看{num}页")n -= numif n <= 0:return index+1if __name__ == "__main__":print('\n输入:')#n = int(input().strip())#pages = [int(item) for item in input().strip().split()]n, pages = 100, [15, 20, 20, 15, 10, 30, 45]print(f"{n}\n{' '.join(map(str, pages))}\n")n = n % sum(pages) # 书总页数对一周计划阅读总量取模。sol = Solution()result = sol.solution(n, pages)print(f"\n输出:\n{result}")input()#03 买苹果
class Solution:def __init__(self) -> None:passdef solution(self, n):result = None# TODO: 请在此编写代码def work(result = n): # 令购买袋数初值为n。''' 穷举所有方案,遴选最少袋数 '''k = 0 # 方案数初值。for i in range(n//8+1): # 用8个一袋遍历,循环次数略少。if (n-i*8)%6 == 0:k += 1 # 方案计数。b = (n-i*8)//6if result > b+i:result = b+iprint(f"\n{k}. {i}+{b}={i+b} (8×{i}={i*8},6×{b}×6={b*6})")return resultresult = work()if result == n:return -1else:return resultif __name__ == "__main__":n = int(input('\n输入购买苹果个数:').strip())sol = Solution()print(f"{'':~^50}\n所有购买组合方案:")result = sol.solution(n)print(f"\n{'':~^50}\n输出购买总袋数:{result}")input() #04 圆桌def table(n, lis):''' 计算桌数和需准备座位数 '''result = 0 # 需求空座位数初值。temp = [] # 相同空座需求客人统计列表初始化。while lis: # 统计同桌客人。tem = [lis[0]]l, r = lis[0]lis.pop(0)for i in lis[:]: # 这里一定要遍历用切片复制lis[:],因为lis可能“动态”变短。li, ri = iif li == r: tem.append(i)lis.remove(i)r = riwhile len(tem) > 1:l_start, ri = tem[-1][1], tem[0][0]if ri == l_start:break # 客人空座链能首尾相接围坐一桌,退出检验循环。else: # 否则,把最后一位客人退回客人空座信息列表lis。lis.append(tem.pop())temp.append(tem)print(f"\n{'':~^50}\n客人分桌信息数组:\n{temp}\n{'':~^50}")for i in temp: # 遍历客人分桌列表,计算同桌客人共用空座。if len(i) == 1:result += max(i[0])continueresult += sum(j[1] for j in i)return len(temp), result + n # 返回客人桌数和需准备的椅子总数(空座数+客人数)。if __name__ == '__main__':n = int(input('\n输入:\n'))lis = [tuple(map(int, input().strip().split())) for i in range(n)]t = table(n, lis)print(f"\n输出:\n{t[1]}\n\n客人需坐{t[0]}桌,共要准备{t[1]}个椅子。")
__上一篇:__ ChatGPT初体验(ChatGPT国内镜像站试用,聊天、Python代码生成)
__下一篇:__
我的HOT博:
- New:ChatGPT初体验(ChatGPT国内镜像站初体验,聊天、Python代码生成。)CSDN质量分92。(30687阅读)
- 尼姆游戏(彩色文字界面版,\033控制码实现。Linux系统有效。)CSDN质量分xx。(1001阅读)
- 神奇的 \033 ,让打印出彩(1739阅读)
- 小炼二维数组(1764阅读)
- 仿真模拟福彩双色球(2622阅读)
- Python之魔幻切片(1417阅读)
- 数列求和a, aa, aaa, ..., aa...aa(n个a)(1729阅读)
- 个人信息提取(2671阅读)
- 中文字符命名Python变量和函数(1021阅读)
- 我的Python学习笔记(1021阅读)
- 十六进制字符串转Python代码(utf-8字符串转十六进制字符串)(1319阅读)
- 生成100个随机正整数(2489阅读)
- 给定字符串提取姓名(字符串、list、re“零宽断言”)(1842阅读)
- 我的 Python.color() (Python 色彩打印控制)(2370阅读)
- python清屏(3150阅读)
- 回车符、换行符和回车换行符(3558阅读)
- Linux 脚本文件第一行的特殊注释符(井号和感叹号组合)的含义(2301阅读)
- random.sample()将在python 3.9x后续版本中被弃用(2045阅读)
- pandas 数据类型之 Series(1809阅读)
- 聊天消息敏感词屏蔽系统(字符串替换 str.replace(str1, *) )(2332阅读)
- 练习:银行复利计算(用 for 循环解一道初中小题)(2159阅读)
- pandas 数据类型之 DataFrame(5932阅读)
- 班里有人和我同生日难吗?(蒙特卡洛随机模拟法)(2921阅读)
- Python 续行符(\)“拯救”你的超长语句(1502阅读)
- Python字符串居中显示(4684阅读)
- 练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)(2331阅读)
- 用 pandas 解一道小题(2268阅读)
- 可迭代对象和四个函数(1752阅读)
- “快乐数”判断(1847阅读)
- 罗马数字转换器(构造元素取模)(3157阅读)
- Hot:罗马数字(转换器|罗生成器)(5783阅读)
- Hot:让QQ群昵称色变的代码(49777阅读)
- Hot:斐波那契数列(递归| for )(4719阅读)
- 柱状图中最大矩形(2348阅读)
- 排序数组元素的重复起止(1964阅读)
- 电话拨号键盘字母组合(2170阅读)
- 密码强度检测器(3124阅读)
- 求列表平衡点(2498阅读)
- Hot:字符串统计(4581阅读)
- Hot:尼姆游戏(聪明版首发)(4135阅读)
- 尼姆游戏(优化版)(1968阅读)
推荐条件 点阅破千
回页首
精品文章:
- 好文力荐:齐伟书稿 《python 完全自学教程》 Free连载(已完稿并集结成书,还有PDF版本百度网盘永久分享,点击跳转免费🆓下载。)
- OPP三大特性:封装中的property
- 通过内置对象理解python'
- 正则表达式
- python中“*”的作用
- Python 完全自学手册
- 海象运算符
- Python中的 `!=`与`is not`不同
- 学习编程的正确方法
来源:老齐教室
回页首
◆ Python 入门指南【Python 3.6.3】
好文力荐:
-
全栈领域优质创作者——寒佬(还是国内某高校学生)博文“非技术文—关于英语和如何正确的提问”,“英语”和“会提问”是学习的两大利器。
-
【8大编程语言的适用领域】先别着急选语言学编程,先看它们能干嘛
-
靠谱程序员的好习惯
CSDN实用技巧博文:
- 8个好用到爆的Python实用技巧
- python忽略警告
- Python代码编写规范
- Python的docstring规范(说明文档的规范写法)