2020 秋招笔试编程题小记

2020 秋招笔试编程题小记

启动机器

工厂中的机器需要花费1时间启动它,每台机器在工作\( t \)时间后会停止,即对于一台机器,启动它之后,它将在\( [x+1,x+t] \)时间内工作。当然,也可以对正在工作着的机器进行“维持启动”,同样花费1时间。

有n个任务需要这些机器来生产,每次生产需要至少有m台机器在工作。现在给出n个任务的到达时间,计算并输出最少需要启动机器的次数。如果无论如何也不能让至少m台机器同时工作,则任务无法完成,此时输出”-1″。

  • \( 1 \leq n,m \leq 1000 \)
  • \( 1 \leq t,w \leq 10^9 \)

测试用例

输入1

2 5 2
1 2

输出1

2

输入2

1 1 10
1

输出2

-1

渡河

阿强一行有N人,第i人的体重为\(a_i\) ,现在阿强一队人面前有一条河挡住了去路,不过他们可以利用小船把大家送到河对岸。这艘船的运动有这样的特性:船最多只能运两人,并且渡河时间(秒)恰等于是两人的体重较大者。现给出阿强一队人的体重,计算阿强最短可能用多久渡河。

输入T组数据,每组数据包含N个正整数,表示这一队人的体重。

测试用例

输入数据

2
4
2 11 9 12
4
2 3 8 7

输出数据

37
19


二叉树计数

一个二叉树有N个结点,给出每个结点所在的深度(根结点的深度为0),计算结点数满足给出的数据的二叉树有多少,由于数据可能较大,输出对\( 10^9 + 7\) 取余的结果。



车辆调度

Alice是某城市的汽车调度员,现在Alice所负责的派车点将为城市A,B两区域派车,每辆车派去A地和B地对于Alice的收益是不同的。Alice的派车点有N辆车,现在分别给出每辆车派去两地的收益,计算向A地派去a辆车以及B地派去b辆车的最大收益。\( 0 \lt a+b \leq N \leq 2000 \).
输入第一行给出N,a,b,接下来N行,每行两个数字分别表示这辆车派去A和派去B的收益。输出一个数字,表示将a+b辆车派至目的地能获得的最大收益。

测试用例

输入数据

5 2 2
4 2
3 3
5 4
5 3
1 5

输出数据

18


编码协议

某种编码协议将数据编为十六进制0-9及A-F,但是’0010’是特殊字串在这种协议中不允许出现,现在给出一串十六进制的数字,判断最少删除几个字符才能使这一串十六进制数中不含有非法字串”0010″

插广告

有N段视频,每段视频长度为\( L_i \)秒,现在要向这N段视频中共计插入M条广告,而两次广告之间不能出现的太频繁否则会降低用户体验,可以在开始前和结束后各插一条广告。计算如何使相邻两条广告出现时间间隔最小值尽可能大,输出这个最大秒数。

数字之和取余

给定n(\( n \leq 35 \))个数字的数组,从中任选k个求和,计算k个数字之和与给定常数m取余可能的最大值。



旅行路线

Alice在暑假游玩了好多地方,但不记得旅行了多少次,根据Alice给出的火车票起始城市,认为城市能首尾相接成为一个闭环则完成一次旅行,计算Alice在暑假中进行了几次旅行。数据保证所有城市都在一个闭环中出现。

测试用例

输入数据

6
beijing nanjing
nanjing guangzhou
guangzhou shanghai
shanghai beijing
fuzhou beijing
beijing fuzhou

输出数据

2


送外卖

Alice是区域外卖调配员,为了让整个区域的外卖员能高效配送,Alice将订单按以小区为单位分组,尽量使外卖员在同一小区多送几份外卖。Alice根据外卖寄送可以知道a订单和b订单是同一小区的。现在Alice有N个小区以及M组数据,统计一下这M组数据中哪些订单都是一个小区,按订单号从小到大输出。这些组中按首个订单号递增的顺序输出。

测试用例

输入数据

5 5
1 2
2 2
3 1
4 2
5 4

输出数据

1
1 2 3 4 5


发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注