作者williamd4112 (Williamd)
看板Prob_Solve
标题[问题] 数列问题
时间Sat Jan 31 17:44:40 2015
原始题目：(非作业)
http://acm.cs.nthu.edu.tw/problem.php?hash=9c16f6606460d1543759fc966b9bb797#
简单叙述一下题目：
给一串有n个数字的数列
以及q个[a,b]的区间
如果第i个区间之後有两个点数总和小於第i个区间的区间,则得到A+的人加1
我的作法
求区间总和：
(1)建立一个n*n的方阵来存
summap[1][2]: 从1 ~ 2的总和
summap[3][6]: 从3 ~ 6的总和
在读取序列时一起进行, 所以花了(n)* (n+1) / 2的时间来进行
(2)读到区间後线性加总
譬如读取到2 6的区间, 就把数列中从[1] ~ [5]的元素加总
最差状况每个区间都是[1, n]的话,需要进行n * q次
储存：
(1)list：
宣告一个struct 来纪录
sum(区间的和),
counter(判断其後是否有两个小於自己的sum的数量)
先把数列完整读入後,建立一个list来存以上的结构
每读入一组区间, 建立一个结构来存,
然後判断读入的这个结构对list中的元素的counter的贡献
(如果conuter == 2则ans++, 之後把该元素从list中erase)
(2)阵列：
建立两个大小为n的阵列,分别存sum, counter
每读取一个区间就扫一次sum阵列
如果sum[i] > sum_current_input则counter++
如果counter == 2时, ans加1次(不会重复加, 因为只有counter < 2时才会递增counter
结果：
summap目前会RE , 还在找问题, 可是summap效能分析起来比线性求和还要差...
所以考虑往别的方向找答案
线性求和的方式搭配list, array都是TLE...
还有哪里可以改进效能的吗？
求和的地方实在想不到其他优化的方法了...
有没有办法减少读取一个区间後, 判断对数列影响的时间呢？
或是有其他方法？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.142.129.2
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1422697483.A.272.html
1F：推 guest2: 你效能分析的结论怪怪的,Q跟N范围一样 01/31 20:51
2F：→ guest2: 两个方法都是O(N^2)吧 01/31 20:52
3F：→ guest2: hint: sum(A...B)=sum(1...B)-sum(1...A-1) 01/31 20:55
4F：→ williamd4112: 阿...看到hint突然好想撞墙...根本就不用方阵来存阿 01/31 22:24
5F：→ williamd4112: 只要花O(n)时间跑一次prefix sum就好............. 01/31 22:24
6F：推 guest2: 另外假设你得到每个人的分数score[1...Q] 01/31 23:11
7F：→ guest2: 从反方向处理会比你从正向用count数更快 01/31 23:14
8F：→ guest2: complexity会从O(QK)=>O(Q) 01/31 23:15
9F：→ guest2: 抱歉 应该是从O(Q^2)=>O(Q) 01/31 23:21
10F：→ williamd4112: 从反向可以做到O(Q)？！如果可希望能提示更多... 02/01 00:05
11F：→ aaaaajack: 先排序一遍找每个人的排位 02/01 02:29
12F：→ aaaaajack: 然後用fenwick tree倒着作回来应该可以做到O(QlogQ) 02/01 02:30
13F：→ aaaaajack: 又或者简单一点用priority_queue维护最小k个数 02/01 02:37
14F：→ aaaaajack: 怎麽做到O(Q)我就比较没概念了，一时之间没想法 02/01 02:37
15F：推 guest2: 关键在於比後面k个人大 02/01 12:21
16F：推 guest2: 第Q-K到第Q个人一定不及格 02/01 12:23
17F：推 guest2: 第Q-K-1要及格要大於後面K个 02/01 12:26
18F：推 guest2: 从Q-K-1到1每个人都要大於後面第K小的 02/01 12:33
19F：推 guest2: 思考如何在新增一个元素进array的同时在O(1)时间找到第K小 02/01 12:40
20F：推 guest2: 当然你必须先花O(K)的时间找到你要的资讯 02/01 12:43
21F：推 guest2: 抱歉 aaaaa大是对的，应该是O(QlogQ) 02/01 14:13
22F：→ guest2: 用priority_queue维护最小k个数才对 02/01 14:14
24F：→ williamd4112: 但当时没有想到说维护k个数字就好xd 02/01 14:52
25F：→ williamd4112: 但这段code还是re了...看来还得花一段时间来debug.. 02/01 14:53
26F：推 guest2: array大小可以动态改变??! 02/01 15:21
27F：→ williamd4112: 上面这段是因为用priority_queue跑RE...想说换个类 02/01 16:34
28F：→ williamd4112: 换成heap来做不知道会不会正确,结果还是re... 02/01 16:34
29F：→ williamd4112: 看了好久没看出哪里可能RE说... 02/01 16:35
30F：→ williamd4112: AC了,原来记忆体很吃紧,不能用long long 02/01 17:08
31F：→ williamd4112: 而seq[n]也是多开的空间,然後sums[n]应该改成sums[q 02/01 17:08
32F：→ williamd4112: 不过看Rank有人可以做到0.001 ... 02/01 17:11
33F：→ williamd4112: 我目前只能做到0.444... 02/01 17:11
34F：推 guest2: 原来 int seq[n]; 这种写法合法啊...我还以为compiler会Er 02/01 18:59
35F：→ guest2: 要解记忆体大小RE的问题可以把变数丢到global变数啦 02/01 19:01
36F：→ guest2: 用long long并没有错，可能的范围-100000000~100000000 02/01 19:02
37F：→ guest2: 本来就应该宣告成long long 02/01 19:03
38F：→ williamd4112: seq[n]那个写法我记得以前上课时也是被告诫过... 02/01 21:38
39F：→ williamd4112: 不过後来compiler都会过就没再去想了,我查看看 02/01 21:39
40F：推 FRAXIS: int seq[n]是C99的功能 找wiki的Variable-length array 02/01 22:22
41F：→ suhorng: C++ 的话就完全是 compiler extension 了 02/02 01:28
42F：推 lmr3796: C99的VLA跟终於可以for(int i;;)是我放下ansi c的关键XD 02/21 00:23