<分区>
问题“规范”:
圣诞节到了!你必须买礼物!
你有一套已经存在的玩具 bundle ，以及 bundle 对应的价格:
1 0 0 1 0 1 1 1 0 => 58
0 1 0 0 1 1 1 0 0 => 27
1 1 1 0 0 0 1 0 0 => 46
0 0 0 0 1 1 1 1 0 => 73
...
1 表示玩具在 bundle 中，0 表示不在 bundle 中。
现在，圣诞老人促销事件即将到来，我们将以“促销特价”向您提供剩余的 bundle X。如果存在另一个 bundle Y，我们会说 X 是一个坏交易，这样:
编辑:为了简化操作，我删除了条件 3，但将条件 1 从“子集”更改为“严格子集”
X是Y 的strict 子集
X比Y 贵
目标是实现一个函数 bool isBadSubset(X)，它可以有效地找出 X 是否良好。
鉴于有数百万个 bundle，将其逐个进行比较显然是不可行的。此外，您可以假设在现有的 bundle 集合中，玩具的子集总是比超集便宜。
提示:
- 比较一个集合是否是另一个集合的子集很容易
- 可以将比较限制为既包含至少
N个玩具 又更便宜 的集合。但是，列表可能仍然很大。 - 朝筛子方向的东西会很好
- 你不需要知道哪个 bundle 更好...只要有一个更好
挑战:是否有可能在恒定时间内实现这一目标？ (与集合中当前的束数量无关)...或至少在 log(n) 中？