洛谷：P3143：Diamond Collector S

题目

P3143：Diamond Collector S

分析

这道题也是一眼的“贪心”题。“大小相对接近”，并给定了任意两颗钻石之间的最大差距K，提醒我们要排序。

那么怎么贪心呢？

贪心策略

首先，需要找到从任意一颗钻石i出发，最多可以包括几颗更小（或者更大）的钻石放在一起，并满足K的约束。此时，有两个要点需要注意：

1. 我们并不关心钻石的价值，而是关心一组钻石的数量。所以，“一组中钻石的数量”才是排序的关键——当然我们也要进行钻石本身大小的排序。
2. 这两个展柜不能展出同一颗钻石，所以，一旦确定第一个展柜的范围，第二个展柜的起点是有限制的。

我用了比较结构化的实现，为的是代码更清晰，但会在同样的复杂度下略微影响执行速度，但在本题中是可行的。

struct Segment {
    int start, end, size;
    Segment(int s, int e) : start(s), end(e), size(e - s + 1) {}

    // 用于排序，按大小降序排列
    bool operator<(const Segment& other) const {
        return size > other.size; // 降序排列
    }
};

sort(diamonds, diamonds + n);

    // 计算所有可能的展示柜段
    vector<Segment> segments;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && diamonds[j] - diamonds[i] <= k) {
            j++;
        }
        j--; // 调整为最后一个满足条件的位置
        segments.push_back(Segment(i, j));
    }

    // 按展示柜大小降序排序
    sort(segments.begin(), segments.end());

我用Segment结构存储了一个合理的钻石包括范围（s/e/size）。为了方便后续排序，size字段是个冗余字段。通过遍历找到每个钻石i所对应的最大范围后，根据Segment.size进行降序排序。

按照贪心的出发点，从最大的size出发，将其作为第一个展柜，然后根据上文提到的要点2找第二个展柜——注意，这一步也还是贪心，只要找到第一个对于第二个展柜来说最大的范围，就可以停止查找。

答案

思考

本题很有意思，是一道纯粹的贪心题，但很容易让人陷入双指针、二分等陷阱。