洛谷题单指南-常见优化技巧-P3143 [USACO16OPEN] Diamond Collector S

原题链接：https://www.luogu.com.cn/problem/P3143

题意解读：找到两个不相交的最长连续序列，使得序列最大值和最小值差不超过k，求两个最长的序列长度和。

解题思路：

先将所有数从小到大排序，记为a[]

要找到两个不相交的最长连续序列，可以采用下面技巧：

设b[i]表示i之前“差值在k之内的连续数的个数”最大值

设c[i]表示i之后“差值在k之内的连续数的个数”最大值

问题关键转换为如何计算b[]，c[]数组

对于b[]数组，通过按顺序遍历a[]，再通过双指针枚举差值在k之内的位置，每次更新找到连续数长度的最大值，并记录下当前位置以前的最大连续长度

对于c[]数组，同理，只不过需要按逆序遍历a[]

有b，c数组，只需要枚举1~n，计算i之前连续数的最大值+i之后的连续数最大值之和，取最大的作为答案即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 50005;

int n, k, ans;
int a[N];
int b[N]; //b[i]表示i之前“差值在k之内的连续数的个数”最大值
int c[N]; //c[i]表示i之后“差值在k之内的连续数的个数”最大值

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int maxn = 0;
    //正序处理得到b[]
    for(int i = 1, j = 1; i <= n; i++) 
    {
        while(j <= n && a[j] - a[i] <= k) 
        {
            j++;
            maxn = max(maxn, j - i); //更新连续数个数的最大值
            b[j] = maxn;
        }
    }
    maxn = 0;
    //逆序处理得到c[]
    for(int i = n, j = n; i >= 1; i--) 
    {
        while(j >= 1 && a[i] - a[j] <= k)
        {
            j--;
            maxn = max(maxn, i - j); //更新连续数个数的最大值
            c[j] = maxn;    
        } 
    }
    for(int i = 1; i <= n; i++)
    {
        ans = max(ans, b[i] + c[i - 1]);
    }
    cout << ans;
   
    return 0;
}