image.pngimage.png

一开始想的是二分去做,推了一些发现映射到坐标轴左右移动上太麻烦了。就转而用双指针了,被边界卡了一上午。整理下思路
首先需要明确的就是往一个方向移动后,最多回头一次,如果回头后再次转向只会浪费策略(既然要再次回头,那为什么不一次性往一条路走呢)
只要明白这一点,这题大概就能从hard降到中等了
如图,以样例2为例
image.pngimage.png
当i指针递增的时候,j也会随之往右拉,因为2(i-startPos)+(startPos-j)必须<=k,显然可以使用滑动窗口来操作
分别枚举以startPos上下界区分的左右两个区间即遍历所有的方案,在其中选择最大的即可。但要注意一些边界情况
如在枚举右窗口i指针时,j有可能越过startPos
image.pngimage.png
当发生这种情况的时候,(startPos-j)可以被丢弃,但(i-startPos)可能是有效的,需要特判一下。处理左窗口的时候同理

每次选取一对i,j后,在预处理好的前缀和中划分区域来得到采摘的水果数(推了好久)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
private int lowerBound(List<Integer> pos,int x){
int l = 0,r=pos.size()-1;
while(l<r){
int mid = l+r>>1;
if(pos.get(mid)>=x) r=mid;
else l = mid+1;
}
return l;
}

public int maxTotalFruits(int[][] fruits, int startPos, int k) {
List<Integer> pos = new ArrayList<>();
int[] sum = new int[fruits.length];


for(int i=0;i<fruits.length;i++){
pos.add(fruits[i][0]);
sum[i] = (i==0?0:sum[i-1])+fruits[i][1];
}
int length = pos.size();
int mid = lowerBound(pos,startPos);
int j = 0;
int answer = 0;
for(int i=mid;i<length;i++){
while(pos.get(j)<=startPos&&2*(pos.get(i)-startPos)+(startPos-pos.get(j))>k) j++;
if(pos.get(j)>startPos){
if(pos.get(i)-startPos<=k)
answer = Math.max(answer,sum[i]-(mid==0?0:sum[mid-1]));
}else if(Math.max(0,2*(pos.get(i)-startPos))+(startPos-pos.get(j))<=k) {
answer = Math.max(answer,sum[i]-(j==0?0:sum[j-1]));
}
}
mid = lowerBound(pos,startPos);
if(pos.get(mid)>startPos) mid--;
j = length-1;
for(int i=mid;i>=0;i--){
while(pos.get(j)>=startPos&&2*(startPos-pos.get(i))+(pos.get(j)-startPos)>k) j--;
if(pos.get(j)<startPos){
if(startPos-pos.get(i)<=k) {
answer = Math.max(answer,sum[mid]-(i==0?0:sum[i-1]));
}
}else if(2*(startPos-pos.get(i))+(pos.get(j)-startPos)<=k){
answer = Math.max(answer,sum[j]-(i==0?0:sum[i-1]));
}
}
return answer;
}
}

image.pngimage.png