广联达笔试

方法：线性二分 + DP

可以将三行输入放在一个大小为n * 3的二维数组nums中，nums[i][0]表示起始时间startTime，nums[i][1]表示送完这单的结束时间endTime，nums[i][2]表示获得的报酬profit。

定义 f[i + 1]表示按照结束时间排序后处理(接单或不接单)前 i 个订单的最大报酬

对于一个外卖订单有两种选择：1.接单 2.不接单

对于第i个订单，

• 不接单：f[i + 1] = f[i]
• 接单，f[i + 1] = f[j + 1] + nums[i][2](报酬)，其中j是满足最大的endTime[j] <= startTime[i]
• 取 接单与不接单所能获得的的最大值,\(f[i + 1] = Math.max(f[i], f[j + 1] + nums[i][2])\)

如果从i往后面遍历，找到符合条件的j，时间复杂度是\(O(n^2)\)，数据有50000，一定会超时。可以通过二分来找到j，时间复杂度为\(O(nlogn)。\)

举例

5
1 3 6 7 11
4 3 4 3 9
2 5 5 3 4

大概长这个样子

1	2	3	4	5
[1,5,2]	[3,6,5]	[6,10,5]	[7,10,4]	[11,20,4]

手动计算一下，按照结束时间排序后：

1. 对于前1个订单，能获得的最大报酬是2
2. 对于前2个订单，能获得的最大报酬是5
3. 对于前3个订单，能获得的最大报酬是: 前2个订单最大报酬 + 5 = 5 + 5 = 10
4. 对于前4个订单，能获得的最大报酬是10: 选择第4个订单获得的最大报酬 < 不选择第4个订单获得的最大报酬
5. 对于前5个订单，能获得的最大报酬是14

代码

package 秋招笔试.广联达0906.第1题;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        int[][] nums = new int[n][3];
        for (int i = 0; i < n; ++i)
            nums[i][0] = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < n; ++i)
            nums[i][1] = nums[i][0] + scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < n; ++i)
            nums[i][2] = scanner.nextInt();
        Arrays.sort(nums, (o1, o2) -> o1[1] - o2[1]);
        long[] f = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            f[i + 1] = f[i];
            int j = bisearch(nums, i, nums[i][0]);
            f[i + 1] = Math.max(f[i + 1], f[j + 1] + nums[i][2]);
        }
        System.out.println(f[n]);
    }

    private static int bisearch(int[][] nums, int r, int start) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid][1] <= start)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }

}