笔试时间为2019年4月14日，五道编程题。编程题如下：
1.变身程序员
题目描述
公司的程序员不够用了，决定把产品经理都转变为程序员以解决开发时间长的问题。
在给定的矩形网格中，每个单元格都可以用以下三个值之一：
- 值0代表空单元格
- 值1代表产品经理
- 值2代表程序员
每分钟，任何与程序员（在四个正方向上）相邻的产品经理都会变成程序员。
返回知道单元格中没有产品经理为止所必须经过的最小分钟数。
如果没有可能，返回-1.
输入描述
不固定多行（行数<=10），每行是按照空格分割的数字（不固定，每行数字个数<=10）
其中每个数组项的取值仅为0,1,2三种
（读取时可以按行读取，知道读取到空行为止，再对读取的所有行做转换处理）
输出描述
如果能够将所有的产品经理变为程序员，则输出最小的分钟数
如果不能够将所有的产品经理变为程序员，则返回-1
示例
示例1
输入：
0 2
1 0
输出：
-1
示例2
输入：
1 2 1
1 1 0
0 1 1
输出：
3
示例3
输入：
1 2
2 1
1 2
0 1
0 1
1 1
输出：
4
分析
- 深度优先搜索，区别在每一次（每分钟）只会将程序员周围的产品经理变为程序员，不会迭代下去
- manage记录产品经理的个数，若每一个传播之后，manage不再变化，停止；
- 若manage=0返回传播时间，反之返回-1。
参考代码
import sys
if __name__ == "__main__":
def get(A):
s=0
for a in A:
for x in a:
if(x==1):
s+=1
return s
lines = sys.stdin.readlines()
a=[]
for line in lines:
a.append(list(map(int,line.split())))
s=0
print("a",a)
manage=get(a)
row=len(a)
col=len(a[0])
def dfs(x,y):
if(x-1>=0 and a[x-1][y]==1):
a[x-1][y]=2
if(x+1<row and a[x+1][y]==1):
a[x+1][y]=2
if(y-1>=0 and a[x][y-1]==1):
a[x][y-1]=2
if(y+1<col and a[x][y+1]==1):
a[x][y+1]=2
return
while(manage>0):
li=[]
for i in range(row):
for j in range(col):
if(a[i][j]==2):
li.append((i,j))
for l in li:
dfs(l[0],l[1])
nmanage=get(a)
print(a)
s+=1
if(manage==nmanage):
break
manage=nmanage
if(manage==0):
print(s)
else:
print('-1')
2.特征提取
题目描述
小明是一个算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x,y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。
因此，如果猫咪特征连续一致，可以认为猫咪在运动。也就是说，如果特征<a,b>在持续帧里出现，那么它将构成特征运动。比如，特征<a,b>在第2/3/4/7/8帧出现，那么该特征形成两个特征运动2-3-4和7-8.
输入描述
第一行包含一个正整数N，代表测试用例的个数
每个测试用例的第一行包含一个正整数M，代表视频的帧数
接下来M行，每一行代表一帧，其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值：比如样例输入第三行里，2表示该帧有两个猫咪特征，<1,1>和<2,2>。所有用例的输入特征总数和<=100000
N满足1<=N<=100000，M满足1<=M<=100000，一帧的特征个数满足<=100000.特征取值均为非负整数
输出描述
对于每一个测试用例，输出特征运动的长度作为一行
示例
示例1
输入：
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1
输出：
3
备注
如果没有长度大于2的特征运动，返回1
分析
- 用字典存储每个特征出现的次数，ans记录特征出现的最大次数，初始为0
- 遍历每一帧的特征，若字典中存在该特征，则次数加一，反正说明该特征断了，次数置为1，更新ans
- 返回ans
参考代码
if __name__ == "__main__":
N=int(input())
for n in range(N):
M=int(input())
d={}
ans=1
for m in range(M):
li=list(map(int,input().split()))
s=li[0]
newd={}
for i in range(s):
ind=(li[i*2+1],li[i*2+2])
if(ind in d):
newd[ind]=d[ind]+1
else:
newd[ind]=+1
for nd in newd:
ans=max(ans,newd[nd])
d=newd
print(ans)
3.机器人跳跃问题
题目描述
机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑—-从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。
起初，机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1建筑。他将会得到或者失去正比于H(K+1)和E之差的能量。如果H(k+1)>E那么机器人就失去H(K+1)-E的能量值，反之它将得到E-H(K+1)的能量值
游戏目标是到达第N个建筑，在这个过程中，能量值不能为负。现在的问题是机器人以多少能量值开始游戏，才可以保证完成游戏
输入描述
第一行输入，表示一共有N组数据
第二个是N个空格分割的整数，H1,H2,H3,...,Hn代表建筑的高度
输出描述
输出一个单独的数表示完成游戏所需的最小单位的初始能量
示例
示例1
输入：
5
3 4 3 2 4
输出：
4
示例2
输入：
3
4 4 4
输出：
4
示例3
输入：
3
1 6 4
输出：
3
备注
数据约束：
1<=N<=10^5
1<=H(i)<=10^5
分析
- 用二分查找来找到最小能量值，start=0，end=max(H),高度小于能量值时，能量只增不减，座椅最大值为max(H);
- 遍历建筑物，更新E值，若中间E小于0，则更新start=mid+1；
- 反之end=mid；
- 最后返回end。
参考代码
if __name__ == "__main__":
N=int(input())
H=list(map(int,input().split()))
start=0
end=max(H)
while(start<end):
mid=(start+end)//2
E=mid
judge=True
for h in H:
if(E < h):
E-=(h-E)
else:
E+=(E-h)
if(E < 0):
start=mid+1
judge=False
break
if(judge):
end=mid
print(end)
4.毕业旅行问题
题目描述
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去以此。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的开销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小花销。
输入描述
城市个数n(1<=n<=20，包括北京)
城市间的车票价钱，n行n列的矩阵m[n][n]
输出描述
最小花销s
示例
示例1
输入：
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0
输出：
13
说明：
共四个城市，城市1与城市1的车费是0，城市1和城市2的车费是2，以此类推，无需考虑极端情况。
分析
- 遍历所有城市，得到每个状态下的最小车费，s是车费，past记录已遍历的城市包含的车票，形如<a,b>是指从a城市到b城市，初始为{(0,0)}，只包含一个城市，车费为0；
- 遍历，新增加一个城市i，遍历所有的车票<a,b>，使得<i,a>+<i,b>-<a,b>最小，即遍历当前城市最小的花费；
- 更新past和s；
- 遍历完，返回s。
参考代码
if __name__ == "__main__":
n=int(input())
m=[]
for i in range(n):
m.append(list(map(int,input().split())))
s=0
past=set()
past.add((0,0))
for i in range(1,n):
a,b=0,0
cost=m[i][a]+m[i][b]
for p in past:
c=m[p[0]][i]+m[p[1]][i]-m[p[0]][p[1]]
if(c < cost):
a=p[0]
b=p[1]
cost=c
s+=cost
past.remove((a,b))
past.add((a,i))
past.add((i,a))
print(s)
4.过河问题
题目描述
将所有人送到河对面，每次只能做2或3个人，且时间是船上人过河时间的最大值。
输入描述
第一行是整数m，表示测试样例格式
每个测试样例的第一行是一个正整数n，表示参加过河的人数；（2<=n<100000）
第二行是n个正整数a[i]（0<a[i]<100000），表示n个人的单独过河时间
输出描述
每个测试样例，输出应该准备的最少过河时间。
示例
示例1
输入：
2
2
1 2
4
1 1 1 1
输出：
2
3
分析
- 用贪心算法来解，分为五种情况，time记录耗时：
- 1人数大于等于7时，按耗时排序得（a,b,c,d,***,m3,m2,m1），先将最耗时的三人送过去，三个同时过去耗时（2d+c+b+m1）,先送过去两个，再送过去一个，耗时（2c+2b+m1+m3）,逐个送过去，耗时（3b+m1+m2+m3），耗时为三种情况的最小值;
- 2人数大于等于6时，按耗时排序得（a,b,c,***,m3,m2,m1），先将最耗时的三人送过去，三个同时过去耗时（2m3+c+b+m1）,先送过去两个，再送过去一个，耗时（2c+2b+m1+m3）,逐个送过去，耗时（3b+m1+m2+m3），耗时为三种情况的最小值;
- 3人数等于五个人时，按耗时排序得（a,b,c,d,e），最大两个先过去后面三个再过去，耗时（e+3c+b）,逐个过去，耗时（e+d+c+2b）;
- 4人数等于四个人时，按耗时排序得（a,b,c,d），耗时（b+c+d）;
- 5人数等与三或二个人时，耗时最大耗时值；
- 返回time。
参考代码
if __name__ == "__main__":
N=int(input())
for i in range(N):
n=int(input())
a=list(map(int,input().split()))
a.sort()
time=0
start=0
end=n-1
while(end-start+1>=7):
p1=a[end]+a[start+1]*2+a[start+2]+a[start+3]*2#过两个小的，再将三个最大的一起过去
p2=a[end]+a[end-2]+a[start+1]*2+a[start+2]*2#过一个小的，将两个最大的过去，再过去一个大的
p3=a[end]+a[end-1]+a[end-2]+a[start+1]*3#逐个过最大的
time+=min(p1,p2,p3)
end-=3
while(end-start+1>=6):
p1=a[end]+a[start+1]*2+a[start+2]+a[start+3]*2
p2=a[end]+a[end-2]+a[start+1]*2+a[start+2]*2
p3=a[end]+a[end-1]+a[end-2]+a[start+1]*3
time+=min(p1,p2,p3)
end-=3
if(end-start+1==5):
p4=a[end]+a[start+1]+a[start+2]*3
p5=a[start+1]*2+a[start+2]+a[start+3]+a[start+4]
time+=min(p4,p5)
end=-1
if(end-start+1==4):
time+=sum(a[start+1:end+1])
end=-1
if(end-start+1>=2):
time+=max(a[start:end+1])
print(time)