广联达-笔试AK题解-2023/09/06

第一题

【简单分析】：

1. 对于订单i，只有两种可能，要么送，要么不送。

2. 若骑手选择送第i个订单，那么在需要耗时time[i]，会影响到后面的i+1 ~ n个订单是否能选择。

因此，为了简化dp过程，遍历的方向应该从后往前，这样做当选择第i个订单时，后面的i+1 ~ n个订单的状态可以转移过来

【状态定义】：

dp[i][0] 表示考虑i ~ n个订单，不送第i个订单，骑手能获得的最大收入

dp[i][1] 表示考虑i ~ n个订单，送第i个订单，骑手能获得的最大收入

例如：若n=15，dp[9][0] 表示考虑第9~15个订单，不送第9个订单，骑手能获得的最大收入

【状态转移】：

//不送第i个订单，那么骑手能获得的最大收入与 i+1 ~ n这些订单的选择与否有关

dp[i][0] = Math.max(dp[i+1][0], dp[i+1][1])

// 送第i个订单，那么骑手能获得的最大收入与 index ~ n这些订单的选择与否有关

// 其中第index个订单表示若骑手送完第i个订单耗时time[i]后最近可以选择的订单

// 第index个订单可能不存在，因为送完第i个订单后耗时time[i]，但是后面没订单可以接了

dp[i][1] = cost[i];

if (checkOrderExist(index)){

dp[i][1] = Math.max(dp[index][0] + cost[i], dp[index][1] + cost[i]);

}

【最终答案】：

Math.max(dp[0][0], dp[0][1])

public static void main(String[] args) throws IOException {
        // 输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] ss1 = br.readLine().split(" ");
        String[] ss2 = br.readLine().split(" ");
        String[] ss3 = br.readLine().split(" ");

        int[][] array = new int[n][3];
        for(int i=0;i<n;i++){
            // 收到第i个订单的时间
            array[i][0] = Integer.parseInt(ss1[i]);
            // 选择送第i个订单的耗时
            array[i][1] = Integer.parseInt(ss2[i]);
            // 选择送第i个订单的收入
            array[i][2] = Integer.parseInt(ss3[i]);
        }
        // 按照收到订单时间的顺序升序排序
        Arrays.sort(array, Comparator.comparingInt(o -> o[0]));

        /* DP */
        // 开long，因为题目给的数据范围很大（单笔订单的收入小于等于1e9）
        long[][] dp = new long[n+1][2];
        dp[n][0] = dp[n][1] = 0;
        for(int i=n-1;i>=0;i--){
            // 不拿当前外卖
            dp[i][0] = Math.max(dp[i+1][0], dp[i+1][1]);
            // 只拿当前外卖，其他的外卖不拿
            dp[i][1] = array[i][2];
            // 拿当前外卖，同时也考虑拿其他外卖
            if((long)array[i][0] + array[i][1] > 1e9){
                continue;
            }
            int index = binSearch(array, array[i][0] + array[i][1]);
            if(index < n && array[index][0] >= array[i][0] + array[i][1]){
                dp[i][1] = Math.max(dp[i][1], dp[index][0] + array[i][2]);
                dp[i][1] = Math.max(dp[i][1], dp[index][1] + array[i][2]);
            }
        }
        System.out.println(Math.max(dp[0][0], dp[0][1]));
    }
    /**
     * 在arr[0~n][0]中找到大于等于target的最小下标
     */
    private static int binSearch(int[][] arr, int target) {
        int l = 0;
        int r = arr.length-1;
        while(l < r){
            int mid = l + ( r - l) / 2;
            if(arr[mid][0] >= target){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        return l;
    }

第二题

1. 由题意得，目标是让所有的士兵外观一致，而我们能做的就是：划出一个偶数长度的区间，从中间切一半，让右半边士兵的外观同化左半边

2. 那么能影响所有士兵外观的就只能是最右边的那个士兵

例：如果前n-1个士兵的外观一模一样，第n个士兵独一无二。虽然我们只有1个士兵外观不一致，但是我们没办法用1次操作使得所有士兵外观一致，因为我们的操作方向是从右影响左。

3. 以最右边的士兵为外观目标，即target = arr[n]

j指针从最右往左走，直到遇到arr[j] != target，这说明第j+1~n个士兵的外观都一样，以这些士兵为右半边让他们直接同化左半边的士兵。

例： [1,2,3,4,5,6,7,8,8,8] -> [1,2,3,4,8,8,8,8,8,8] -> [8,8,8,8,8,8,8,8,8,8]

public static void main(String[] args) throws IOException {
        // 输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(ss[i]);
        }

        // 双指针 + 贪心
        int ans = 0;
        int target = arr[n-1];
        int i = n-1;
        int j;
        while(i >= 0){
            j = i;
            while(j >= 0 && arr[j] == target){
                j--;
            }
            if(j < 0){
                break;
            }
            ans++;
            int rightCount = n - j - 1;
            i = j-rightCount;
        }
        System.out.println(ans);
    }