题目
分析
这道题也是一眼的“贪心”题。“大小相对接近”,并给定了任意两颗钻石之间的最大差距K
,提醒我们要排序。
那么怎么贪心呢?
贪心策略
首先,需要找到从任意一颗钻石i
出发,最多可以包括几颗更小(或者更大)的钻石放在一起,并满足K
的约束。此时,有两个要点需要注意:
- 我们并不关心钻石的价值,而是关心一组钻石的数量。所以,“一组中钻石的数量”才是排序的关键——当然我们也要进行钻石本身大小的排序。
- 这两个展柜不能展出同一颗钻石,所以,一旦确定第一个展柜的范围,第二个展柜的起点是有限制的。
我用了比较结构化的实现,为的是代码更清晰,但会在同样的复杂度下略微影响执行速度,但在本题中是可行的。
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找第二个展柜——注意,这一步也还是贪心,只要找到第一个对于第二个展柜来说最大的范围,就可以停止查找。
答案
思考
本题很有意思,是一道纯粹的贪心题,但很容易让人陷入双指针、二分等陷阱。
这题是我和太太出门去美国(6月14号)前的最后更新。在美国我应该不会更新洛谷刷题。