问题:
我有 n 个向量的输入:
(x, y, z): x ∈ {1..n},y ∈ {1..n},z ∈ {1..n} (every "dimension" is set(1..n))
*I mean that in one vector x,y,z can be the same(x=y=z),
but for ∀v1,v2 => x1≠x2, y1≠y2, z1≠z2
v1>v2 if and only if x1>x2,y1>y2,z1>z2.
lets denote vector v1 "minimal" if and only if ∄v ∈ input: v>v1
任务是计算输入中的最小向量。
资源:
我在本地编程竞赛的任务中发现了这个问题。
(翻译后的)公式是:
n people participeted in competion. competion had three phases(every competitor
took part in every stage). denote that the participant is better then
participant b, if a ranks in all three stages is higher then participant b ranks.
participant c is the best, if there is no such participant who is better
than participant c. output the number of best participants.
1<=n<=100000 时间限制:1 秒。
我的尝试和想法
第一个想法是创建类 Result(用于竞争对手的结果),重载运算符 >(或 <),就像:
bool operator > (const Score &s) const
{
if (first_result > s.first_result)
if (second_result > s.second_result)
return third_result > s.third_result;
return false;
}
并构建任何基于数组(例如最小堆),允许找到最小值(使用<)并计算它们(我认为我只是按照这种方式“重新创建”了堆排序的错误变体)。在我这次尝试失败后,我尝试了 Fenwick 树(二进制索引树)来完成相同的任务。
但是后来我明白我的方法是不正确的(不是 ok 类和 < 重载),并且将任务转换为 1d 的想法根本不好。
然后我找到了一些关于 BIT & Segment Tree for n-dimensions case 的信息,我认为我可以用它们来解决这个问题。但是我很难实现工作变体(甚至在 1d 内理解段树的工作原理)
也许有人可以帮助实施(或找到更好的解决方案并解释它)?