[Leaf] [P3143] Diamond Collector S

p3143-[usaco16open]-diamond-collector-s---洛谷">P3143 [USACO16OPEN] Diamond Collector S - 洛谷

1. 题面梗概

中译中：在一堆钻石里选出两组。每组内部最大值的和最小值的差值不能超过 $K$。两组不能共用钻石。求最多能选多少颗。

2. 逻辑推导

无序的钻石很难处理，我们先进行升序排序。

这样题目要求的 极差 $\leq K$ 就等价于 区间左右端点差 $\leq K$。

这时，我们只需要在数组上用双指针维护一个区间。

2.1 前后缀分解

题目要求选两个不相交的区间。直接暴力枚举两个区间的起点终点复杂度会爆炸。

既然区间不相交，那么必然存在一个 分界点：$i$。

• $i$ 左边：我们能选出的一个最大区间（前缀最优）。

• $i$ 右边：我们能选出的一个最大区间（后缀最优）。

我们只需要枚举每一个可能的分界点，把两边的 最优解 加起来即可。

2.2 结论

双指针扫描 + 前后缀 DP 预处理。将全局的最优解拆解为两个局部的最优解之和。

3. 代码实现

▶

AcCode

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

const int maxn = 5e4 + 50;

int a[maxn];
int pre[maxn], suf[maxn];
int n, k, l, r;

int main( ) 
{
    cin >> n >> k;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];

    sort( a + 1, a + n + 1 );

    l = 1, r = 1;
    while( r <= n )
    {
        while( a[r] - a[l] > k && l <= r ) l ++;
        pre[r] = max( pre[r - 1], r - l + 1 );
        r ++;
    }

    l = n, r = n;
    while( l >= 1 )
    {
        while( a[r] - a[l] > k && l <= r ) r --;
        suf[l] = max( suf[l + 1], r - l + 1 );
        l --;
    }

    int ans = 0;
    for( int i = 1; i < n; ++ i )
    {
        ans = max( ans, pre[i] + suf[i + 1] );
    }

    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：$O( N \log N )$，瓶颈在排序。

• Trick：两区间不相交 -> 前后缀分解 这个技巧。

• 关联笔记： 双指针