广联达-笔试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);
}
#笔试##秋招##广联达#
查看2道真题和解析
