2021年滴滴春招笔试题-测试工程师

一、选择题（20道题）

计算机基础相关题目

二、编程题（2道）

1、任务调度算法

贪心解决

        时间限制： 3000MS
        内存限制： 589824KB
        题目描述：
        优秀的操作系统离不开优秀的任务调度算法。现在，有一台计算机即将执行n个任务，每个任务都有一个准备阶段和执行阶段。只有在准备阶段完成后，执行阶段才可以开始。同一时间，计算机只能执行一个任务的执行阶段，同时可以执行任意多个任务的准备阶段。请你设计一个算法，合理分配任务执行顺序，并输出完成所有任务的最少时间。
        输入描述
        第一行一个整数n表示任务的数量（15*10^4）
        接下来n行每行两个整数a，b表示第i个任务的准备时长和执行时长。（110^9）
        输出描述
        仅一行一个整数，表示执行所有任务的最少时间。
        样例输入 2  5 1  2 4  样例输出 7 

2、施展魔法

          时间限制： 3000MS
          内存限制： 589824KB
          题目描述：
          小A的家门口有一排树，每棵树都有一个正整数的高度。由于树的高度不同，来到小A家的朋友都觉得很难看。为了将这些树高度变得好看，小A决定对其中某些树施展魔法，具体来说，每施展一次魔法，可以把一棵树的高度变成任意正整数（可以变高也可以变低）。

          小A认为，这排树如果能构成等差为x的等差数列就好看了。但是小A不想施展太多次魔法，他想知道最少施展魔法的次数。

          形式上来说，小A家门口一共有n棵树，第i棵树高度为ai。小A最后的目标为对于任意2≤i≤n，ai-ai-1=x



          输入描述
          输入第一行包含两个正整数，n和x，含义如题面所示。

          输入第二行包含n个正整数，第i个数的含义为第i棵树的高度ai


          范围：n≤105,1≤ai≤105，x≤1000

          输出描述
          输出包含一个正整数，即小A最少施展魔法的次数


          样例输入
          5 2
          1 3 1 3 5
          样例输出
          3

          提示
          对3,4,5号树施法，最后变为1,3,5,7,9