洛谷:P3143:Diamond Collector S


洛谷:P3143:Diamond Collector S

Table of Contents

题目

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找第二个展柜——注意,这一步也还是贪心,只要找到第一个对于第二个展柜来说最大的范围,就可以停止查找。

答案

Solution

思考

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

这题是我和太太出门去美国(6月14号)前的最后更新。在美国我应该不会更新洛谷刷题。

Previous Next