问题:
我有 n 个 vector 的输入:
(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
任务是计算输入中的最小 vector 。
来源:
我在本地编程竞赛的任务中发现了这个问题。
(翻译的)公式是:
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 class 和 < overload)并且 mb 在 1d 中转换任务的想法一点也不好。
然后我找到了一些关于 BIT 和 n 维情况下的线段树的信息,我认为我可以用它们来解决这个问题。但是我很难实现工作变体(甚至在超过 1d 的情况下理解线段树的工作原理)
也许有人可以帮助实现(或找到更好的解决方案并进行解释)?
最佳答案
首先,我们需要一个有序的键/值数据结构,您可以插入、删除和查找小于或等于您自己时间的上一个/最后一个值 O(log(n))
。想想红黑树或 btree 或跳跃列表。
我将为该数据结构使用以下发明的符号。我故意让它看起来不像任何真实的语言。
by_order.prev(key)
给出与最大键相关联的 k-v 对 <= to key
。
by_order.prev(key).k
给出最大的键 <= to key
。这可以是 None
。
by_order.prev(key).v
给出与最大键相关联的值 <= to key
。
by_order.next(key)
给出与最小键关联的 k-v 对 >= 到 key
with .k
和 .v
表示他们之前所做的。
by_order.add(key, value)
添加一个 k-v
对。
by_order.del(key)
删除值为 key
的 k-v
对。
思路是这样的。我们首先按 x
排序,然后按 y
排序,然后按 z
排序。第一个 vector 是最小的。如果它的 z
值小于 z
的最低值,则之后的每个 vector 都是最小的,对于任何具有小于或等于 y
的元素。我们将使用 by_order
数据结构来测试该条件。
假设我没有出错,这是伪代码:
sort(vectors) by x then y then z
Declare and initialize your empty ordered data structure by_order
// NOTE: by_order[val] will be the value of the largest key <= val
answer = [] // ie an empty list
answer.push(vectors[0])
by_order.add(vectors[0].y, by_order[vectors[0].z)
for v in vectors:
z_best = by_order.prev(v.y).v
if z_best is None or v.z < z_best:
answer.push(v) // Yay!
// Clear anything in by_order that we are an improvement on
while True:
pair = by_order.next(v)
if pair.v is not none and pair.k < v.z:
by_order.del(pair.v)
else:
break
// and now we add this one to by_order.
by_order.add(v.y, v.z)
排序的总时间是O(n log(n))
。
后面是每个 n
vector 的 O(log(n))
查找以查看是否插入它,可能后面是 O(1 )
插入到答案中,O(log(n))
查找仍然跟随它的内容(别担心,我没有忘记那些被删除的),接着是 O(log(n))
插入,接着是 O(log(n))
检查发现这个需要删除,然后是 O(log(n))
删除。
这是很多 O(log(n))
项,但总和仍然是 O(log(n))
。 n
次。
结果是整个问题的O(n log(n))
算法。
关于c++ - 计数 "minimal"个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49053427/