现在这个是对的了,emmm (20190520)
我的想法是这样的:
此时已经把银行按照距离排序过了。
劫匪A,B从左边开始遍历每个银行,A用一个变量记录他造访过的银行里,最富有的有多少钱,B用一个变量记录,他如果打劫他面前的银行,再加上A访问过的银行里最富有的那家银行,最高能打劫多少钱;
这里,A只负责造访银行,每次由B来决定要不要打劫
大致规则就在上面,然后代码如下
private int rob_1(Bank[] banks, int d){
int cur_max_money = 0;
int n = banks.length;
int ans = 0;
int left = 0; int right = 1;
// 先把右指针拉到第一个满足题目要求的点,然后开始遍历
while(right < n && banks[right].location - banks[left].location < d){
right++;
}
while(right < n){
// 右指针不能越界
while(left < right && banks[right].location - banks[left].location >= d){
// 此时左点和右点之间的距离满足要求,同时,左边所有的点都和右边这个点之间距离满足要求
// 该while循环保证了抢劫 1. right当前指向的银行 2. 包括left在内的 左边的任意一家银行 的所有方案是合法的
// 更新一下左边银行最多的钱
cur_max_money = Math.max(cur_max_money, banks[left].money);
left++;
}
// 此时left距离right过近,right继续向右遍历
// 这时,跟新一下最后的解
// 即当前银行的钱加上前面满足要求的银行的钱的最高值
ans = Math.max(ans, cur_max_money + banks[right].money);
right++;
}
return ans;
}
(之前的遗留内容,已废弃,20190520)
我想了一下应该没问题啊,但是就是过不了,而且还容易超时,emmm,麻烦各位大佬帮我看一下这个思路有啥问题