题目大意
题目会给出一个序列aaa,我们需要遍历序列aaa的所有连续子序列。
在所有连续子序列当中,找到符合条件的子序列,统计数量
判断子序列是否符合条件的因素为:
1. 该子序列当中的所有数的平均数avgavgavg跟子序列当中某一个数字相等,该子序列即为符合条件。
我们需要去找出有几个这样的子序列,判断,输出即可。
举个例子,现在有个子序列为[1,2,3,4,5][1,2,3,4,5][1,2,3,4,5],他的平均数为avg=3avg = 3avg=3 ,刚好在子序列当中有一个数字为3,那么现在这个子序列就是一个合法的子序列。
思路解析
首先,我们得找出所有子序列,然后才能去查看是否符合条件,那么我们可以解题步骤分为两步去做。
1. 通过枚举的方式,枚举出所有的连续子序列
2. 判断连续子序列是否合法
根据这两步,我们可以先去拟定出对应的伪代码
我们将这份核心代码分成三部分来进行分析
1. 枚举左区间的循环 O(n)
2. 枚举右区间的循环 O(n)
3. 检查是否合法 O(n)
在这样的情况下,我们的时间复杂度为O(n3)O(n^3)O(n3),当n=100n = 100n=100的时候,我们可以通过题目,但是在n>=1000n >= 1000n>=1000的时候,我们会出现超时的情况。
现在评测机一秒钟运算的计算次数大约在10810^8108的层级当中。
时间复杂度优化
1. 枚举左右区间的目的是为了遍历所有子序列,假若更改替换,我们很难保证会有子序列被漏算的情况,同时因为输入序列是无序的,你也无法保证在其中可能出现特殊的子序列情况,因此,左右区间我们是没有办法去进行替换优化的
2. 检查是否合法,我们的判断依据为[l,r][l,r][l,r]是否存在一个ai=avga_i = avgai =avg的情况。如果我们可以不用循环就得知关系式是否存在,那么循环就可省去。 恰好我们学过一个东西,叫做桶排序,或者说计数法。
计数方法,一旦将所有的数字保存在对应桶当中,在知道桶的下标的情况下,我们的查询效率为O(1)O(1)O(1),而在此处avgavgavg就为桶的下标,同时因为数值最大不过300030003000,因此桶的数量也可以开辟出来。 那么,优化后,时间复杂度为O(n2)O(n^2)O(n2)。
每一段子序列配上一套计数桶,那么我们在每次枚举之前记得清空即可。