【拼多多2019】避嫌抢劫。

1、题目描述

小镇沿街分布（可以理解为都在数轴上），有n家银行（位置以数轴的坐标表示，金额表示可以被抢走的金额）。

两个绑匪试图分别抢劫一个银行，为了让警方多奔波他们商定选择的两个银行距离不小于d。

请问，符合约定的情况下他们能抢到的总金额最大是多少。

输入格式

输入包含 n+1 行。
第一行包含两个整数 n 和 d，分别表示银行的数量和约定的距离。
接下来 n 行，每行包含两个整数 a 和 b ，分别表示坐标和金额。

输出格式

输出一个数字表示可以获得的最大金额。

数据范围

注意：数据中保证至少存在两个银行之间的距离不小于 d。

输入样例：

6 3
1 1
3 5
4 8
6 4
10 3
11 2

输出样例：

11

2、问题描述：

3、问题关键：

• 双指针做法。
• 按照坐标进行排序。然后i，j指针（j < i)，依次向后移动，如果距离大于d那么，判断计算当前i坐标下符合距离的最大的j的位置的取值。
• 暴力做法：对于每一个i，都让j从头开始进行循环，求解。
• 优化：因为对距离进行了排序，所以，如果对于i符合的j，那么i + 1对j也都符合，所以j就不用从头移动。

4、C++代码：

暴力：

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int n, d;
PII banks[N];

int main()
{
    cin >> n >> d;
    for (int i = 0; i < n; i ++ ) cin >> banks[i].first >> banks[i].second;
    
    sort(banks, banks + n);
    
    int res = 0;
    for (int i = 0; i < n; i ++) {
        int maxv = 0;
        for (int j = 0; j < i; j ++) {
            if (banks[i].first - banks[j].first >= d) 
                maxv = max(maxv, banks[j].second);
        }
        res = max(res, banks[i].second + maxv);
    }
    
    cout << res << endl;
    
    return 0;
}

优化：

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int n, d;
PII banks[N];

int main()
{
    cin >> n >> d;
    for (int i = 1; i <= n; i ++ ) cin >> banks[i].first >> banks[i].second;
    
    sort(banks + 1, banks + 1 + n);//对距离进行排序。
    
    int res = 0;
    for (int i = 1, j = 0, maxv = 0; i <= n; i ++ )
    {
        while (j + 1 < i && banks[i].first - banks[j + 1].first >= d)
        {
            j ++ ;
            maxv = max(maxv, banks[j].second);//符合距离的求，对于当前i最大的j对应的钱。且对于i + 1， j也继续向后移动，之前的maxv值依然符合，因为，如果后面的距离符合，那么前面的距离肯定比这个更远，故也符合。
        }
        
        res = max(res, banks[i].second + maxv);
    }
    
    cout << res << endl;
    
    return 0;
}