题解 P3143 【[USACO16OPEN]钻石收藏家Diamond Collector】

EarthGiao · 2019-10-10 10:38:37 · 题解

【思路】

排序 + 双指针

【前缀思想】

很有意思的一道题目
这个需要找两组差不超过k的并且和最大的序列
因为需要差不超过k，
所以可以先将序列排一下序
然后就成为了有序的序列（很显然对吧）
这样就可以用双指针记录头和尾
然后只要头和尾的差小于等于k
就可以尝试一下这个区间能不能再扩大
所以可以很简单的就用双指针找出最长的差小于等于k的序列

【中心思想】

但是，这道题目有两个陈列架
所以找出一个最大的是不行的
而且找出次大的和最大的加起来也是不可行的
因为不保证最大和次大的区间不重叠
所以可以正序扫一遍然后找出
到每一个点之前最长的差小于等于k的序列
然后再倒序找一遍找出
到每一个点之后最长的差小于等于k的序列

【小细节】

这样，只需要再枚举一遍每一个点
然后比较前后加起来的和最大的就是了
不过，如果出现了前后最大的刚好重叠在枚举到的这个点
那么加起来的和就会重复一次
而且是不合法的
毕竟你不能把一个宝石放在两个陈列架上
所以就有了后面在比较时候的：
M = max(M,qian[i] + hou[i + 1]);
这样就不会出现一个点刚好是两个区间的交点的情况了

【完整代码】

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int Max = 50005;
int a[Max];
int qian[Max];
int hou[Max];
int main()
{
    int n,k;
    cin >> n >> k;
    for(register int i = 1;i <= n;++ i)
        cin >> a[i];
    sort(a + 1,a + 1 + n);
    for(register int l = 1,r = 1;r <= n;++ r)
    {
        while(a[r] - a[l] > k && l <= r)l ++;
        qian[r] = max(qian[r - 1],r - l + 1);
    }
    for(register int r = n,l = n;l >= 1;l --)
    {
        while(a[r] - a[l] > k && l <= r)r --;
        hou[l] = max(hou[l] + 1,r - l + 1);
    }
    int M = 0;
    for(register int i = 1;i < n;++ i)
        M = max(M,qian[i] + hou[i + 1]);
    cout << M << endl;
    return 0;
}