拼多多面试题

多多最近在研究一种由n个数字构成的特殊数组X={x1，x2，…xn}，这个数组有2个特点:
1.X数组是严格递增的，也就是 x1 2.X数组的相邻数字间做差值，得到新数组Y是严格递减的。换句话说，用y(i)=x(i+1)-x(i);表示相邻数字间差值，则新数组Y={y1，y2, yn-1} 满足: y1> y2> …> yn-1,
现在，假设只有数字n、数组的第一个数字的值a=x1以及数组最后一个数字的值b=xn的情况下，多多想知道能不到找到任意1个这样的特殊数组，同时满足上面两个条件。

输入描述

第一行，一个整数T，表示测试用例的组数。(1<=T<=3000)
接下来每组测试用例包含一行数据，由3个数字构成，分别是:n,a,b (1<=n<= 400, 1<= a <=b<=1000)，分别表示:数组的长度、第一个数字的值、最后一个数字的值。

输出描述
每组测试用例，输出一行:
YES 或者NO表示:是否存在任意1个这样的数组。

示例1

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

输出

YES
NO
YES
1
2
3

说明
共有3组测试用例，
对于第1组用例，可以找到数组:[1,4,5] 满足数组本身是严格递增的，数组相邻数字之间的差值 [3,1]是严格递减的，所以输出:YES

对于第2组用例，严格递增的数组是:[1,2,3,4,5]，但是数组相邻数字之间差值构成的数组[1,1,1,1]不满足严格递减，所以输出:NO

对于第3组用例，可以找到数组:[1,40,70,90,100] 满足数组本身严格递增，数组相邻数字之间的差值 [39,30,20,10] 满足严格递减，所以输出:YES

第2题

多多君从小到大都没有谈过恋爱，因此他希望大家都能成双入对，包括数字。现在他有一串数字，他希望其中的数字能两两匹配。能够两两匹配的数字满足如下要求:
1.他们之间差的绝对值大于等于一个特定值
2.他们没有出现在其他数字对中，即每个数字只能被匹配一次或零次
现在，多多君希望能知道，给定一串数字，最多可以匹配成功多少对数字对

输入描述
第一行，2个整数N，M，分别表示数字的个数和要求数字间的差异值(1<=N<=2000000,0<=M<=10^9)
接下来一行，由N个整数构成，分别表示第i个数字Xi。(0<=Xi<= 10^9)

输出描述
一个数字，表示在给定的数字中，能匹配的最多数字对个数

示例1

输入

4 2
1 3 3 7
1
2

输出

2
1

说明
可以匹配最多2个数字对(1,3)和(3,7)

示例2
输入

5 5
10 9 5 8 7
1
2

输出

1
1

说明
可以匹配最多1个数字对(5,10)，其余数字对都不满足差的绝对值大于等于5
备注
对于40%的数据，有1<=N<=1000
对于50%的数据，有1<=N<=50000
对于100%的数据，有1<=N<=2000000

第3题

多多君在矾究一种特殊的01矩阵，即一个N * M的二维矩阵中，每个元素只能是0或者1。
多多君将原始矩阵A进行一种特殊变换来创造一个新矩阵B，其中两个矩阵的行和列保持一致。

对于第i行第j列的元素(编号从1开始)，生成规则如下:
B[i][j]=maz(A[i][1],A[i][2].…,Ai, A[1][j],A[2][j]… A[N][j])
即B[i][j]的值为A[i][j]所在的同一行和同一列的所有元素中的最大值。
多多君经过分析发现，通过矩阵A计算得出矩阵B比较容易，那是否能快速通过矩阵B还原得出矩阵A呢。

输入描述
第一行，1个整数T，代表测试用例的组数。
( 1 <= T <= 20 )
对于每组测试用例:
第一行:2个整数N和M，表示矩阵的行和列。
( 1 <=N <= 100, 1 <= M <= 100 )
接下来N行M列，其中第(行第)列表示给定的炬阵B的元素B(月0I
( 0 <= B[i][j] <= 1 )

输出描述
对于每组测试用例:
如果可以通过矩阵B还原得到矩阵A，那么输出所有可能的矩阵A中，最多能有多少个值为1的元素。
否则输出-1，表示距阵B无法还原得到巨阵A。

示例1
输入

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

输出

-1
1
2
1
2
3

对于第一组用例，不存在矩阵A可以得到该矩阵B。
对于第二组用例，满足条件的矩阵A只有一个:
0 0 0
0 1 0
所以该矩阵值为1的元素只有1个。

对于第三组用例，满足条件的矩阵A有:
1)1 1
2)1 0
3)0 1

而其中第一个矩阵A有最多值为1的元素，共2个。

第4题

多多君计划周末去骑行，不过他的自行车目前年久失修，有很多部件都坏了。多多想在出发前把它修好。
对于每个部件，多多可以选择修理，也可以选择直接挽。直接换比修理花的时间少一点，但是花的钱多一点。
多多想知道怎么安排修理计划，才能在出发前修好他的自行车并且花的钱最少。

输入描述
第一行两个整数，N、M分别代表坏的部件数和多多可以用于修车的时间。(1 <= N <= 40, 1 <= M <= 10000000)
接下来有N行，每行有4个整数Ai、Bi、Ci、Di，分别代表第i个部件, 修理需要花的时间，修理需要花的钱，直接换需要花的时间，直接换需要花的钱。(1<=Ci

输出描述
输出一个整数，代表在M时间内修好自行车，需要花的最少金钱，如果不能在M时间内修好，输出-1

示例1
输入

1 10
10 2 3 5
1
2

输出

2
1

说明
选择修理，时间花费10，金钱花费2

示例2
输入
复销

1 10
12 2 3 5
1
2

输出

5
1

说明
修理这个部件需要时间花费是12，时间不够，只能选择换，时间花费3，金钱花费5

示例3
输入

3 18
9 1 2 11
8 4 3 10
10 6 5 12
1
2
3
4

输出

23
1

选择修第一个部件，第二、三个部件直接换，总时间花费9+3+5=17，金钱花费1+10+12=23