s*****g
发帖数: 5159 | 1 不是想得那么简单,倒腾晕了.
有一组整数对，(,, ....,)，用
vector >实现。
现在需要去处所有满足下列条件的数对：
如果piwj，那么去除i
如果pi>pj且wi
保证最后的vector满足上述条件，且没有删除任何不需要删除的元素。
k不大，所以k^3复杂度可以接受。
谢谢大家。 | c*m
发帖数: 1114 | 2 这不就是一个排序问题么？
对 p_i 排序，O(klogk)复杂度
排完后新vector是,...
然后对w_i*按照i从大到小遍历一遍，如果w_(i+1)*（就是
从右向左测试w_i*是个递减数列，碰到不对的话删除左节点。) 复杂度o(k) (当然你也
可以从左到右遍历，反正记得出了问题就删除左节点就行。)
总复杂度O(klogk+k)=O(klogk)?
【在 s*****g 的大作中提到】
: 不是想得那么简单,倒腾晕了.
: 有一组整数对，(,, ....,)，用
: vector >实现。
: 现在需要去处所有满足下列条件的数对：
: 如果piwj，那么去除i
: 如果pi>pj且wi: 保证最后的vector满足上述条件，且没有删除任何不需要删除的元素。
: k不大，所以k^3复杂度可以接受。
: 谢谢大家。
| s*****g
发帖数: 5159 | 3 最开始也是这样想的，实验发现不对，现在想了一个，这个稍有改动。
每次删除左节点以后要继续往左比，看看是不是要删除更左的节点，什么时候不能删了
，再往右扫描。
就是
【在 c*m 的大作中提到】
: 这不就是一个排序问题么？
: 对 p_i 排序，O(klogk)复杂度
: 排完后新vector是,...
: 然后对w_i*按照i从大到小遍历一遍，如果w_(i+1)*（就是
: 从右向左测试w_i*是个递减数列，碰到不对的话删除左节点。) 复杂度o(k) (当然你也
: 可以从左到右遍历，反正记得出了问题就删除左节点就行。)
: 总复杂度O(klogk+k)=O(klogk)?
| X****r
发帖数: 3557 | 4 你两个条件不是一回事吗？
这个关系是传递的，换句话说你建立了一个partial order，你要找它产生的
maximal elements，是吧？这个硬做也只要O(k^2)吧，有什么不简单的地方吗？
【在 s*****g 的大作中提到】
: 不是想得那么简单,倒腾晕了.
: 有一组整数对，(,, ....,)，用
: vector >实现。
: 现在需要去处所有满足下列条件的数对：
: 如果piwj，那么去除i
: 如果pi>pj且wi: 保证最后的vector满足上述条件，且没有删除任何不需要删除的元素。
: k不大，所以k^3复杂度可以接受。
: 谢谢大家。
| c*m
发帖数: 1114 | 5 是呀，所以这个是右节点优先，推荐你从右像左扫描就很完美了。
【在 s*****g 的大作中提到】
: 最开始也是这样想的，实验发现不对，现在想了一个，这个稍有改动。
: 每次删除左节点以后要继续往左比，看看是不是要删除更左的节点，什么时候不能删了
: ，再往右扫描。
:
: 就是
| s*****g
发帖数: 5159 | 6 多谢,这是十几天脑子不转,不知道为什么.
【在 c*m 的大作中提到】
: 是呀，所以这个是右节点优先，推荐你从右像左扫描就很完美了。
| s*****g
发帖数: 5159 | 7 是传递的,只是数据结构上,每次删掉一个节点,就要小心变化用来比较的两个指针.
【在 X****r 的大作中提到】
: 你两个条件不是一回事吗？
: 这个关系是传递的，换句话说你建立了一个partial order，你要找它产生的
: maximal elements，是吧？这个硬做也只要O(k^2)吧，有什么不简单的地方吗？
|
|
