滴滴笔试
记录一下滴滴笔试，还比较简单，不知道为什么第二题只过了80% 测试样例
第一题
小钟有一个长度为 n的数组 a，以及一个选代程度 d。
每一天这个数组都会按照如下方式进行一次选代:
对于每个数字x，假设其大小在数组中所有元素中的从大到小的排名为k，
当k≤d 时，数字x不变; 否则，数字x变成选代前数组排名为k-d 的元素。 注意，数组中元素出现的次数不影响排名，选代过程中每个数字的更新是同时进行的。
例如，对于数组[2,2,1,5]，对数组中元素从大到小排名[5,2,1]，排名第一大的元素是5，第二大的元素是 2，第三大的元素是1。
当 d=1 时，第一次选代后原数组变为[5,5,2,5]，第二次送代后原数组变为[5,5,5,5]
现在小钟想知道，给定选代程度d，对于长度为n 的数组a ，在经过 10^100 天选代后，最终的数组会选代成什么样。请你计算并输出最终的数组。
输入
第一行有两个整数$n\ (1 \leq n \leq 2 \times 10^5),\ d\ (1 \leq d \leq 200)$ ，分别表示数组长度、选代程度.
第二行有一行 n个整数a1,a2… an表示题目中给定的数组。
对于所有数据，满足$1 \leq n \leq 2 \times 10^5,\ 1 \leq d \leq 200,\ 1 \leq a_j \leq 10^9$.
输出
输出一行n个整数，相邻两数用空格隔开，表示经过 $10^{100}$ 天选代后的数组。
样例输入
1
2
4 1
2 2 1 5
样例输出
1
[5,5,5,5]
解题思路
因为$10^{100}$ 太大了，所以不能暴力模拟，需要找规律。
基本上是按照规律从小到大排一下，然后按照d截一下，然后把后面的数映射到前面的数上。
1
2
3
4
def array_iter(arr, d):
sorted_set = list(sorted(set(arr), reverse=True))
map_dict = {sorted_set[i]: sorted_set[i%d] for i in range(len(sorted_set))}
return [map_dict[i] for i in arr]
第二题
小美最近在上几何课时接触到了三角形的相关概念， 作为课后作业，任课老师给大家安排了一个有趣的问题。
假设我们现在希望构成n个三角形，并且目前每个三角形已经确定了两条边。 现在，需要用n条刻余的边来完成这些三角形。
其中，这 n条边中第i条边的长度为 a[i] 。
小美的任务是找到在最优情况下，能够组装出多少个不退化的三角形(即每个三角形的三条边长度满足三角形不等式，参见样例解释)。
输入
第一行1个整数T，表示数据组数。 对于每组数据:
第一行包含一个整数 n，表示三角形的数量,
第二行包含 n 个墪数 b1[1], b1[2],.. b1[n]
第三行包含n个数 b2[1],b2[2],…. b2[n]
b1[i],b2[i] 表示第i个三角形已确定的两边。
第四行包含n个墪数a[1], a[2],…, a[n]。表示剩余的 n 条边。 $1 \leq T \leq 5,\ 1 \leq n \leq 50000,\ 1 \leq a[i], b1[i], b2[i] \leq 10^9$
输出
输出T行分别表示每组数据管案:
对每组数据，输出一行一个整数，表示最多能组成的没有退化的三角形的数量。
样例输入
1
2
3
4
5
6
7
8
9
2
3
3 5 2
4 7 6
1 2 3
1
2
6
3
样例输出
1
2
2
0
解题思路
可以先按照 构成三角形的要求： $a-b < c < a+b$ 找到符合要求的边，然后按照匈牙利匹配算法，找到最大匹配数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def is_non_degenerate(s1, s2, s3):
return s1 + s2 > s3 and s1 + s3 > s2 and s2 + s3 > s1
def solve(b1, b2, a):
n = len(b1)
adj = [[] for _ in range(n)]
for i in range(n):
for j in range(n):
if is_non_degenerate(b1[i], b2[i], a[j]):
adj[i].append(j)
match = [-1] * n
result = 0
for i in range(n):
visited = [False] * n
if can_match(i, adj, match, visited):
result += 1
return result
def can_match(u, adj, match, visited):
for v in adj[u]:
if not visited[v]:
visited[v] = True
if match[v] < 0 or can_match(match[v], adj, match, visited):
match[v] = u
return True
return False
if __name__ == "__main__":
t = int(input())
for i in range(t):
n = int(input())
b1 = list(map(int, input().split()))
b2 = list(map(int, input().split()))
a = list(map(int, input().split()))
count = solve(b1, b2, a)
print(count)
也可以调包