菜鸟春招实习笔试题解(0530)

type

status

date

slug

summary

📝 主旨内容

帖子顺序(贪心)

题目描述：

菜鸟物流网站上有几个帖子，第n个帖了被ai个人点赞，被bi个人点踩。第i个帖子的好评度为ai-bi。

现在有m个人来看帖子，你可以安排他们按顺序看帖子。前一个人只有看完所有帖子才能到后个人看。当第j个人看到好评度大于等于ci的帖子时就会点赞，反之则会点踩。

现在请你安排一个看帖子的顺序，所有帖子的好评度之和尽可能大，输出这个好评度。

输入描述

第一行输入一个整数n(1≤n≤1000)

第二行输入n个整数ai(1≤ai≤10^9)

第三行输入n个整数bi(1≤bi≤10^9)

第四行输入一个整数m(1≤m≤1000)

第五行输入m个整数c(1≤ci≤10^9)

输出描述

一行一个整数，表示最大好评度之和。

样例输入

样例输出

提示

最优安排的顺序为[1,3,2]。所有人看完帖子之后的帖子好评度分别为[5,-4,-4,-2,6]。

💡

将C数组从小到大排序之后模拟即可，其他语言注意需要开long long

错排的最小交换次数(思维)

题目描述:

小红有一个排列，她想让这个排列变成错排，她每次可以换两个相邻的数，求最小的操作次数。

排列的定义是：一个长度为n的数组p，1到n每个数正好出现一次。

错排的定义是：不存在pi=i的排列

输入描述

第—行输入—个整数n（1≤n≤10^5）表示数组长度。

第二行输入n个整数表示排列ai(1≤ai≤n)。

输出描述

输出一个整数表示答案。

样例输入

样例输出

提示

交换第二第三个元素，排列变成: 2, 3, 1 是一个错排。

💡

不要想太多了，首先看第一个位置，如果它是1，那么只能和下一个数进行交换，可以发现交换完成之后这两个数一定符合错排的条件，比如1 2交换后是2 1，或1 3交换后是3 1

💡

从左往右去考虑，只有最后一个数会向左交换，和刚刚说的一样，一旦发生交换，交换后的两个数一定符合错排。并且重复交换会复原，每次只需要操作一次即可，就能得到最小操作次数

走到最后的最小体力(最短路)

有几个石头排成一排，第i个石头的高度为ai。

当小红站在一个高度为x的石头上时，当且仅当满足以下条件时可以跳到一个高度为y的石头:

1.y是x的倍数，那么小红跳到高度为y的石头上，花费体力为y/x 2.x是y的倍数，那么小红跳到高度为y的石头上，花费体力为x/y 也就是说每次跳的距离可以是任意的，只要高度符合要求即可。例如，石头的高度分别为[3,6,9,2]，小红在第一块石头上，可以跳到第二块石头，花费体力为 6/3=2，也可以跳到第三块石头，花费体力为 9/3 =3，但是不能跳到第四块石头，因为2不是3的倍数或因子。

小红想从第一个石头跳到第n个石头。她想知道最少需要花费多少体力?

输入描述：

第一行输入一个正整数n，代表石头的数量。

第二行输入几个正整数ai，代表每个石头的高度, 1 ≤ n, ai ≤ 50000

输出描述:

如果无法从第一个石头跳到第几个石头，则输出-1。否则输出一个整数，代表最少需要花费的体力。

样例输入1:

样例输出2:

提示:

先跳到第二个石头，花费2体力。再跳到第三个石头，花费3体力。总花费体力为 5。

样例输入2:

样例输出2:

样例输入3:

样例输出3:

💡

抽象一下就是问从节点1到节点n的最短距离，两点之间存在双向边当且仅当两数存在倍数关系

💡

首先看如何建图，n最大是50000，双重循环去判断倍数的不可行的。可以枚举每个数的倍数，只要倍数在给定的列表内就连接一条双向边。并且是用邻接表存图，点数很大无法用邻接矩阵存储

💡

然后看如何求最短路，n很大朴素版Dijkstra是O(n^2)的pass。可以发现边数是很小的，直接采用堆优化Dijkstra即可

💡

最后看几种特殊情况，首先是样例中提到的单个点的情况，开局就到终点了直接返回0。其次是题目并没有说每个石子的高度是唯一的，所有可能出现3 1 3 这时应该返回1，直接从起点到终点，如果没有注意到这种情况会直接返回0。简单分析可以得出，这种“瞬移”只有当节点数不为1且起点和终点相等时才会触发，否则同值传递没有任何意义，存在花费1

🤗 总结归纳

整体难度不高，第二题不需要想太多就好

📝 主旨内容

帖子顺序(贪心)

错排的最小交换次数(思维)

走到最后的最小体力(最短路)

🤗 总结归纳

📎 参考文章