本期题单：缴纳过路费，纯职业小队
文章目录
- 缴纳过路费
- 题目
- 思路分析
- 代码
- 纯职业小组
- 题目
- 思路分析
- 感谢大伙观看，别忘了三连支持一下
- 大家也可以关注一下我的其它专栏，同样精彩喔~
- 下期见咯~
缴纳过路费
题目
题目链接：缴纳过路费
思路分析
这一题就是很典型的 并查集 的题目了，它就是一个找父节点的思路流程。
对于并查集，本篇就不说了，后面会出一期来讲它的，如果对这个算法陌生的话可以学习一下这个大佬的文章：跳转链接，这位大佬讲的很好，我也是学习的他的文章。
下面就针对这道题分析一下 ——
题目里面比较需要注意的点 ——
- 过路费是指最大价值，而不是总和
- 过路费要处于上下限之间
- 道路是双向的
规则一 和 规则二，就意味着如果有一条路的价值超过上限，那就不需要考虑它。对于低于下限的道路，可以和符合条件的道路共存，但不能单独存在。
规则三意味着没有直接连接的两个地方也能够到达。
OK，大概就是这些内容，然后我们针对下面这组数据来分析一下
6 8 2 7
1 2 2
1 3 5
2 3 8
1 4 1
2 4 5
2 5 4
3 4 9
2 6 1
其中 2 - 3 和 3 - 4这两条路超过了最大价值，可以在存储的时候直接去除掉，我们用不到它。
然后 1 - 4 和 2 - 6这两条路低于最低价值，我们需要记录一下，不能让它们单独出现。
uf1是低于上限的，uf2是低于下限的
他们的一个路径大致如下图 ——
也就是说——
（1，2）（1，3）（1，4）（1，5）（2，3）（2，4）（2，5）（3，4）（3，5）（4，5）
任选两个城市都是符合的，所以我们只需要知道符合的城市的总数，然后就能直接计算：
n * (n - 1) // 2
然后还需要注意类似uf2这样结构的，就是两个独立的分支，两边都需要计算。
低于上限的所有路径 - 只包含低于下限的路径
这样就能够计算上所有符合的了。
OKK，下面看看代码吧。
代码
class UnionFind:def __init__(self, n):self.pre = [i for i in range(n)] # 记录父节点self.size = [1] * ndef find(self, x): # 寻找根节点if x != self.pre[x]: # 判断父节点是不是自己本身rx = self.find(self.pre[x]) # 向上寻找父节点self.pre[x] = rxreturn rxreturn xdef union(self, x, y): # 组合/连接两个节点rx, ry = self.find(x), self.find(y)if rx == ry: # 如果两个数的父节点是相同的就直接返回returnself.pre[ry] = rx # 这里互换也是一样的，不考虑内部结构self.size[rx] += self.size[ry] # 记录以它为根节点的所有子树def cal(num):return num * (num - 1) // 2n, m, l, r = map(int, input().split())
uf1 = UnionFind(n + 1)
uf2 = UnionFind(n + 1)
for i in range(n):u, v, w = map(int, input().split())if w <= r: # 比上限小的才存进来uf1.union(u, v)if w < l:uf2.union(u, v)ans = 0
for i in range(1, n + 1):if i == uf1.find(i):ans += cal(uf1.size[i])if i == uf2.find(i):ans -= cal(uf2.size[i])
print(ans)
纯职业小组
题目
题目链接：纯职业小组
思路分析
这道题就是去考虑最差情况，题目情况很多，我们一点点来分析。
首先我们对各个小组人数进行一个分类 ——
- 比3小的，这个就直接加上去就行了
- 比3大的，余数是 0 的，如果被用完 + 0，没用完 + 2
- 比3大的，余数是 1 的，如果被用完 + 1，没用完 + 2
- 比3大的，余数是 2 的，这个无论有没有被用完，都可以直接 + 2
给大家一个例子
1
2 2
1 8
3 4
你们按照上面的逻辑去写，就知道怎么个事儿了。
然后对于 所能组成的队伍数 - k（需要组成的队伍数） 如果 大于兵种数，那么就需要加上 2 * 兵种数，如果小于兵种数就需要进行更麻烦的计算了。
if k <= y2:ans += 3 * k + (y0 + y1) * 2 + y2 * 2
elif k <= y1 + y2:x = y1 + y2 - kans += 3 * k + (y0 + x) * 2 + y2 * 2 + (y1 - x)
elif k <= y0 + y1 + y2:x = y0 + y1 + y2 - kans = 3 * k + x * 2 + y2 * 2 + y1
大概就是这么回事。
然后和大伙说一下就是我的代码没有完全实现，至少在我对这道题目的理解下，但是能够解决题目测试点，但是整体思路应该是对的。
t = int(input())
for _ in range(t):n, k = map(int, input().split())A = {}z = 0for __ in range(n):a, b = map(int, input().split())if a in A.keys():A[a] += belse:A[a] = bgroup = ans = 0y0 = y1 = y2 = 0for i in A.keys():if A[i] >= 3:group += A[i] // 3if A[i] % 3 == 0: # 余数为0y0 += 1elif A[i] % 3 == 1: # 余数为1y1 += 1elif A[i] % 3 == 2: # 余数为2y2 += 1else:ans += A[i] # 比3小的队伍直接加z += 1if k > group:print(-1)else:if group - k > n: # 测试样例全是这里的值ans += k * 3 + 2 * (len(A.keys()) - z)print(ans - 2)else:if k <= y2:ans += 3 * k + (y0 + y1) * 2 + y2 * 2elif k <= y1 + y2:x = y1 + y2 - kans += 3 * k + (y0 + x) * 2 + y2 * 2 + (y1 - x)elif k <= y0 + y1 + y2:x = y0 + y1 + y2 - kans = 3 * k + x * 2 + y2 * 2 + y1print(ans)
感谢大伙观看，别忘了三连支持一下
大家也可以关注一下我的其它专栏，同样精彩喔~
下期见咯~
