之前面试华为，弄过两次机考，将其记录下来，侵权则删。

第一次机考

1. 无尽的任务

小杰在工作中有很多任务，为了保持高效，小杰在同一时间内只处理一项任务。在当前交付周期里，有n个任务（1<=n<=1000）,每个任务的价值为vi(1<=vi<=1000)，需要完成的时间为（1<=ti<10000）,最后期限为di(1<=di<=1000),超过最后期限完成则产生不了任何价值，球，求小杰能输出的最大价值是多少。

解答要求：

时间限制：C/C++ 1000ms,其他语言：2000ms
内存限制：C/C++ 256MB,其他语言：512MB

样例 1

输入

1
2
3
4
3
3 3 10
1 1 10
10 10 10

输出

1
10

解释：

前两个任务价值和才6，第三个是10，如果选择前两个任务的任何一个，那就完成不了第三个任务。所以只要选择第三个任务去完成，就可以获取最大的任务价值。

样例2

输入

1
2
3
4
3
6 5 4
5 1 5
5 5 10

输出

1
10

解释

结果是选择第一个和第三个任务。选择第一个任务花了5个单位的时间，第二个任务需要在期限5以前完成，所以选择不了，只能再选择第三个任务。

2. 开门次数

小明家有座超级大房子，有很多房间，用数字编号，房间之间有门，门打开后会自动关上，使用空格分隔的房间号roomJ,roomK，代表了roomJ和roomk之间有门，可以来回。假如小明身处房间roomA,需要去往指定房间roomB，请给出最少需要开几次门才能到达。

解答要求：
时间限制：C/C++ 1000ms,其他语言：2000ms
内存限制：C/C++ 32MB,其他语言：64MB

输入

第一行是当前所处房间roomA.

第二行是目的地房间号roomB.

第三行是门的数量N.

第四行开始的N行，是使用空格分隔的两个房间号，代表一扇门。

说明：

1<=门的数量<=100

房间号为int数字

输出

最少开门次数

样例1

输入

1
2
3
4
5
6
7
8
1
5
5
1 2
2 3
3 4
2 5
4 5

输出

1
2

解释：小明从房间1到房间2，房间2到房间5，最少开两次门就可以达到。

提示

题目确保有解。

第二次机考

1. 最小设备能力

在一段笔直的公路上，需要部署相同规格临控设备组中分别给出了需要监控的点位和监控设备安装的点位（点位用距位置0的距离描述）。
求解部署的监控设备的最小覆盖范围为多少，才能确保安装点位覆盖需要监控的点位

特别注意：客监控点监控设备的规洛完全相同
解答要求
时间限制：C/C++1000ms，其他语言：2000ms
内存限制：C/C++256MB，其他语言：512MB

输入
第一行为一个整数N，表示总共需要监控的点位数量；
第二行为N个整数（单空格间隔），分别表示这N个需要监控点位的坐标点；
第三行为一个整数M，表示允许安装的点位数量；第四行为M个整数（单空格间隔），表示允许安装设备的坐标点；

输出
设备需要最小覆盖距离

样例1

输入：

1
2
3
2
1 5
3

输出：
1
2

解释：
1.输入参数：总共需要覆盖的点位数为2，分别为点位1和5；总共需要部署的监控设备数是1，监控点位是3；
2.点位3与点位1距离为2，点位3与点位5距离为2；
3.设备最小覆盖的距离为2

样例2

输入：

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

输出：
1
2

解释：
1输入参数：总共需要覆盖的点位数为4，分别为点位1，235；总共需要部署的监控设备数是2，监控点位是2.5；
2点位2与点位1或点位3的距离为1，点位2与点位2的距离为0，点位5与点位5的距离为0；
3.由于设备覆盖距离相同，要保证监控点位2覆盖周边点位，最小距离为1；

提示:
1.需要监控的点位个数最大不超过500；
2.需要安装监控设备的点位个数不超过500；
3.各个点位用整数表示，最大不超过UINT32，即OxFFFFFFFF=4294967295；
4.输入点位可能存在乱序的情况；

2. 单词的组合

析文章中相邻两个单词之间搭配关系，其规则如下：
1.找出文章中出现次数最多的单词，（可能多个单词出现次数并列第一）。
2.包含该单词（规则1找出的单词）的出现次数最多的单词组合。
3.按字典序输出这些单词组合，如果没有符合条件的单词组合输出NULL。
注意：
1.单词：未被标点符号或者空隔断的连续字母是一个单词。
2.单词只包含小写字母，最长不超过100个字母。
3.单词组合：2个相邻的单词，2个单词之间只能用1个空格分割。
4.用2个及以上空格分割的2个单词不是单词组合。
5.用非空格的符号分割的2个单词不是单词组合。
6.包含A的单词组合：A可能在前面，也可能在后面。
7.出现次数最多的单词可能没有单词组合。

解答要求
时间限制：C/C++1000ms，其他语言：2000ms
内存限制：C/C++32MB，其他语言：64MB

输入：
第一行开始给出一个长字符串，长度小于2048。
输入只包合小写字母、空格、常见标点符号（”、、（、y、），不包含大写字母、数字、换行符。

输出：
第一行开始，按字典序输出字符串。

注意：
1.输出请按字典序排列。（字典序是基于字母顺序排列的单词按字母顺序排列的方法。）
2.输出请去掉重复的单词组合。
3.如果符合题目要求的输出或者输出为空，请输出NULL。

样例1

输入：how,are you
输出：NULL

解释：找不到符合条件的字符串，输出”NULL”。
注意：are和you之间有2个空格

样例2

输入：helo word hijackhow are u hello cat helo dog
输出：cat hello hello cathello dog hello word u hello
解释：
字符串中出现次数最多的单词是“hello”
包含hello”的单词组合中”cat hello”””elo cat，”hello dog””hello wo rd”，”u hello”出现次数都为1次并列最多
输出按字符串的字典序输出。
注意:jackhow因为单词之间使用非空格分割，所以不是一个单词组合。

样例3

输入：aa.bb.bb.cc dd eeff
输出：NULL
解释：出现次数最多的单词是bb，但是没有相应的单词组合

样例4

输入：aa bb cc dd
输出：

1
2
3
aa bb
bb cc
cc dd

解释：
出现次数最多的单词为“aa””bb””cc””dd”
包含这些单词的组合有aa bb””bb cc”ccddr”这些组合出现的次数都为1次。

3. 求覆盖村落所需要的基站数

运营商拟在广阔的荒湾地区部营站，该地感到划为MN个方格，其中分布看×个村溶（每个村落占用一个方格）。已知每个基站能够盖益。个方格的正方形区域，求覆盖所有村落至少需要建立几个基站。
解答要求
时间限制C/C++3000ms，其他语言：6000ms
内存限制：C/C++64MB，其他语言：128MB
输入：
第一行为两个整数M和N（O<M.N<100000），代表矩形地区的大小；第二行为一个整数×（0<X<=20），代表村落数量；接下来有X行，每行有两个整数m和n（0<=m<M，0<=n<N），代表一个村落的坐标
输出：
输出一个整数，代表覆盖所有村落至少需要的基站个数。

样例1

输入：

1
99999 999992001000010000

输出：2
解释：有两个村落，坐标分别为（0，0）和（10000，10000）。它们相累甚远。
无法用同一个其站覆盖，要覆盖它们至少需要两个基站

样例2

输入：

1
2
3
4
10 10 
2
2 6
4 8

输出：1
解释：有两个村落，坐标分别为（2，6）和（4，8）。若在坐标为（3，7）的方格设置一个基站，以该方格为中心的3×3的区域能够覆盖所有村落，故只需一个基站即可。