蓝桥杯备考冲刺必刷题（Python） - 3611 冒险者公会

大家好，我是讯享网，很高兴认识大家。

学习Python从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（Python） | 汇总-CSDN博客

【题目描述】
一个地区包含 $n$ 个村庄，每个村庄发布了一些委托任务，需要冒险者的帮助。
冒险者公会共有 $m$ 位冒险者。某位冒险者具有能力值 $x_i$ ，这表示他能够完成难度值小于等于 $x$ 的委托任务。每位冒险者最多只能出击一轮，在这一轮中，他们可以不重复地通过若干个村庄。
当一名冒险者路过一个村庄时，他最多只能完成该村庄的一个委托任务，且这个委托的难度不能超过冒险者的能力值。冒险者也可以选择在路过一些村庄时不完成任何委托任务。同样的，每个委托任务只需要被完成一次。
无论冒险者完成多少任务，这名冒险者出击一轮的代价都等同于冒险者的能力值。
现在的目标是确定一种冒险者的出勤方案，以使得完成所有村庄的委托任务的总代价最小。
【输入】
第一行输入两个整数 $m$ 和 $n$ ，分别表示冒险者的数量和村庄的数量， $0\lt m,n\le 10^3$ 。
第二行 $m$ 个整数 $x_1,x_2,\dots x_i,\dots x_m$ ，代表每位冒险者的能力值， $0\lt x_i\le 10^3$ 。
接下来 $n$ 行，每行代表一个村庄，每行第一个整数k表示该村庄的委托数量，此后 $k$ 个不大于 $10^3$ 的正整数表示该村庄的每个委托任务的难度值， $0\lt k\le 10^3$ 。
【输出】
在一行中输出一个整数，表示完成所有委托所需的最小总代价。如果不能完成所有的委托，则直接输出 $- 1$ 。
【输入样例】

讯享网

3 4 2 9 6 2 3 7 1 5 3 2 2 3 3 1 1 1

讯享网

【输出样例】

讯享网17

【代码详解】
[图片]

import sys level = [0 for i in range(1005)] city = [[0 for i in range(1005)] for i in range(1005)] mx = [0 for i in range(1005)] m, n = [int(i) for i in input().split()] ls = [int(i) for i in input().split()] for i in range(1, m+1): level[i] = ls[i-1] level1 = sorted(level[1:m+1]) # 冒险者按照能力从小到大排序 level = level[0:1] + level1 + level[m+1:] for i in range(1, n+1): ls = [int(j) for j in input().split()] k = ls[0] if k>m: # 如果委托比冒险者人数还多，那么一定不能完成 print(-1) sys.exit() for j in range(1, k+1): city[i][j] = ls[j] city1 = sorted(city[i][1:m+1]) # 每个村庄的任务从小到大排序 city[i] = city[i][0:1] + city1 + city[i][m+1:] for i in range(1, m+1): # 每一轮都完成每个村庄里最难的一个任务，记录每一轮的最难任务的代价 unit = city[1][i] # 定义一个临时值 for j in range(1, n+1): # 遍历n个村庄 if unit<city[j][i]: # 擂台法，求得每个村庄的最难任务 unit = city[j][i] mx[i] = unit mani = 1 cityi = 1 ans = 0 while cityi<=m and mx[cityi]==0: # 得到cityi的起始值（不为0） cityi+=1 while mani<=m and cityi<=m: # 双指针查看是否能否完成所有任务 if mx[cityi]<=level[mani]: # 如果某个人能完成这轮中所有村庄最难的任务，那么这一轮所有村庄的任务就肯定能全部完成 cityi+=1 # 轮数自增1 ans += level[mani] # 加上这个冒险者的能力值 mani+=1 # 不管这个人能否完成这个村庄的任务，都换下个人（如果没完成，cityi不增加） if cityi==m+1: # 如果完成所有委托则输出总代价 print(ans) else: print(-1)

【运行结果】

讯享网3 4 2 9 6 2 3 7 1 5 3 2 2 3 3 1 1 1 17

蓝桥杯备考冲刺必刷题（Python） - 3611 冒险者公会

相关推荐