求解今年校赛F题怎么做？

2017/4/10镜像同步39 回复

求解今年校赛F题应该怎么做？题目意思其实就是一个数组n个数，然后对于每个指定的数求它前边位置的比他小的最大的数，没有就是0，然后最后相加就是结果（第一个数对应0）样例1: 1, 2, 3 则就是0 + 1 + 2 = 3 样例2: 3， 5，1， 2， 4 则就是0 + 3 + 0 + 1 + 3 = 7 虽然有同学讲题了但是还是没听懂，希望会做的同学能够仔细再讲下，十分感谢！

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

ken19931108机器人#1 · 2017/4/10

请问还能在线提交吗？

dxy1机器人#2 · 2017/4/10

【在 ken19931108 的大作中提到: 】 : 请问还能在线提交吗？现在还不行，估计过段时间会挂上去的

Wizmann机器人#3 · 2017/4/10

每年一道卡STL的题吗？。。。

ken19931108机器人#4 · 2017/4/10

【在 dxy1 的大作中提到: 】 : : 现在还不行，估计过段时间会挂上去的 soga

lxclxc机器人#5 · 2017/4/10

正常的思路会超时O(n^2)，我猜可以用hash表或者二叉查找树？毕竟这是一个查找问题。

dxy1机器人#6 · 2017/4/10

【在 lxclxc 的大作中提到: 】 : 正常的思路会超时O(n^2)，我猜可以用hash表或者二叉查找树？毕竟这是一个查找问题。讲题的同学说是用树状数组处理下，但是没想明白怎么处理？

gungnir机器人#7 · 2017/4/10

【在 dxy1 的大作中提到: 】 : : 讲题的同学说是用树状数组处理下，但是没想明白怎么处理？其实就是构造一个线段树，维护区间最大值和最小值，然后二分搜索就好了，每次操作都是logn复杂度

dxy1机器人#8 · 2017/4/10

【在 gungnir 的大作中提到: 】 : 其实就是构造一个线段树，维护区间最大值和最小值，然后二分搜索就好了，每次操作都是logn复杂度维护最大和最小值的话怎么找出来比当前值小的最大的那个数呢？

l11x0m7机器人#9 · 2017/4/10

set和upper_bound配合使用，应该是O(nlogn)复杂度