小马智行pony.ai 2019校招真题（二）
时长:120分钟 总分:100分
93浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 3 |
1.
新增的专线
Pony.ai 有N个office分布在不同地方(编号从0开始），某些office之间有部署专线，office之间可以通过专线间接连接（专线是双向的），例如guagnzhou和beijing之间有专线，guagnzhou和shenzhen之间有专线，那么beijing可以通过guangzhou与shenzhen间接地通讯，这条信路的总延时是两条专线的延时之和。两个office之间的通讯延时是他们之间延时最短的信路的延时。
Infra团队知道当前任意两个office之间的通讯延时。最近Infra团队希望在office a与 office b之间部署一条新的专线，希望这条专线的延时 t 尽可能大（出于成本考虑）同时延时最大的两个office之间的通讯延时与 t 之和小于k，你能帮忙求出这个 t 吗？ 输入描述： 第一行一个正整数 N <= 1000，表示office的数目
接下来N行，每行N个非负整数，用空格分开。第i行第j个数表示当前office i和office j之间的通讯延时，保证小于1e9。
接下来一行3个整数，依次表示a，b，k。其中
。输入样例：
3
0 2 3
2 0 5
3 5 0
1 2 3 输出描述：
输出一行一个整数，满足条件的t，注意t不能是负数。如果不存在满足条件的t，输出 -1。输出样例
0
Infra团队知道当前任意两个office之间的通讯延时。最近Infra团队希望在office a与 office b之间部署一条新的专线，希望这条专线的延时 t 尽可能大（出于成本考虑）同时延时最大的两个office之间的通讯延时与 t 之和小于k，你能帮忙求出这个 t 吗？ 输入描述： 第一行一个正整数 N <= 1000，表示office的数目
接下来N行，每行N个非负整数，用空格分开。第i行第j个数表示当前office i和office j之间的通讯延时，保证小于1e9。
接下来一行3个整数，依次表示a，b，k。其中
。输入样例：
3
0 2 3
2 0 5
3 5 0
1 2 3 输出描述：
输出一行一个整数，满足条件的t，注意t不能是负数。如果不存在满足条件的t，输出 -1。输出样例
0
2.
谁挡住了我的红绿灯
命运的十字路口前，有
辆车在等红灯。还来不及思考此刻的选择会将他们带向何方，司机们发现了一个更现实的问题——由于车的高度不尽相同，某些车会因前车的遮挡而无法看到红绿灯。这时候，“谁挡住了谁的红绿灯”便成为一个……很好的笔试题！
现已知红绿灯高度为
，
辆按距离红绿灯由近到远分别标号为
，第
辆车与红绿灯的距离为
，高度为
。为简化问题，我们以距红绿灯的距离为x轴，高度为y轴建立平面直角坐标系，则红绿灯可抽象为一点
，第
辆车可抽象为线段
。我们称车
挡住了车
的红绿灯，当且仅当
，且车
看红绿灯的视线，即
与
的连线与代表车
的线段
相交（含两端）。
，辆按距离红绿灯由近到远分别标号为，第辆车与红绿灯的距离为，高度为。为简化问题，我们以距红绿灯的距离为x轴，高度为y轴建立平面直角坐标系，则红绿灯可抽象为一点，第辆车可抽象为线段。我们称车挡住了车的红绿灯，当且仅当，且车看红绿灯的视线，即与的连线与代表车的线段相交（含两端）。 现在，我们需要你对每辆车计算谁挡住了它的红绿灯；即对于每一辆车
，求最大的
满足“车
挡住了车
的红绿灯”。
输入描述：
第一行包含两个非负整数，求最大的满足“车挡住了车的红绿灯”。 
和
；第二行包含
个非负整数
。输入样例：
9 5
5 4 3 4 3 3 3 3 3 输出描述：
输出共有
行，第
行包含对于车
的答案，若没有车挡住车
，则该行输出0。输出样例
0
1
2
1
4
4
4
4
1
3.
最大正整数
数组中存储了一堆小于10的非负整数，整个数组从左到右代表一个正整数（如数组[0, 1, 3, 2]代表正整数132）。现给出一个正整数K，要求经过K次数组相邻位置元素交换（必须完成K次交换），使得这个数组代表的数字最大。
例如,
int array[] = {0, 1, 3, 2}, K = 1，则经过1次交换后，数组所能代表的最大值为1032；
int array[] = {0, 1, 3, 2}, K = 2，则经过2次交换后，数组所能代表的最大值为3012。
输入描述：
首先，输入一个正整数T，表示接收T组测试用例；此后，输入T组测试用例，其中每组测试用例包含如下内容：
输入1：一个正整数K，表示在当前测试用例中，可以对数组进行K次相邻元素间的位置交换；
输入2：一个正整数N，表示当前用例包含数组的长度；
输入3：N个数组元素，所有元素都是小于10的非负整数；输入样例： 4 2 5 4 2 1 3 5 3 5 4 2 1 3 5 4 5 4 2 1 3 5 5 5 4 2 1 3 5 输出描述： 输出共N行，对应于N个用例的输出：
每行输出为一个数组，数组元素之间用一个空格隔开，要求每行输出前后均无多余空格。输出样例 4 3 2 1 5 4 5 2 1 3 5 4 2 1 3 5 4 2 3 1
