T2-1:草药丛?陷阱!
2024-10-01 14:07:53
发布于:天津
题目大意
题目会给出一个序列,我们需要遍历序列的所有连续子序列。
在所有连续子序列当中,找到符合条件的子序列,统计数量
判断子序列是否符合条件的因素为:
- 该子序列当中的所有数的平均数跟子序列当中某一个数字相等,该子序列即为符合条件。
我们需要去找出有几个这样的子序列,判断,输出即可。
举个例子,现在有个子序列为,他的平均数为 ,刚好在子序列当中有一个数字为3,那么现在这个子序列就是一个合法的子序列。
思路解析
首先,我们得找出所有子序列,然后才能去查看是否符合条件,那么我们可以解题步骤分为两步去做。
- 通过枚举的方式,枚举出所有的连续子序列
- 判断连续子序列是否合法
根据这两步,我们可以先去拟定出对应的伪代码
int count = 0 ; // 累加符合条件的子序列
for(int l = 1 ; l <= n ; l ++ )
{
// 使用一个for循环,代表目前枚举的左边界
double sum = 0 ;
for(int r = l ; r <= n ; r ++ )
{
// 代表当前枚举的右边界
sum += a[r] ; // 累加区间的每一个元素
// 当前两个for循环代表枚举出来的区间[l,r]
double avg = sum / (r-l+1) ; // 获取平均数
for(int i = l ; i <= r ; i ++ )
{
if(avg == a[i]) count ++ ;
}
}
}
我们将这份核心代码分成三部分来进行分析
- 枚举左区间的循环 O(n)
- 枚举右区间的循环 O(n)
- 检查是否合法 O(n)
在这样的情况下,我们的时间复杂度为,当的时候,我们可以通过题目,但是在的时候,我们会出现超时的情况。
现在评测机一秒钟运算的计算次数大约在的层级当中。
时间复杂度优化
-
枚举左右区间的目的是为了遍历所有子序列,假若更改替换,我们很难保证会有子序列被漏算的情况,同时因为输入序列是无序的,你也无法保证在其中可能出现特殊的子序列情况,因此,左右区间我们是没有办法去进行替换优化的
-
检查是否合法,我们的判断依据为是否存在一个的情况。如果我们可以不用循环就得知关系式是否存在,那么循环就可省去。 恰好我们学过一个东西,叫做桶排序,或者说计数法。
计数方法,一旦将所有的数字保存在对应桶当中,在知道桶的下标的情况下,我们的查询效率为,而在此处就为桶的下标,同时因为数值最大不过,因此桶的数量也可以开辟出来。 那么,优化后,时间复杂度为。
每一段子序列配上一套计数桶,那么我们在每次枚举之前记得清空即可。
#include<bits/stdc++.h>
using namespace std;
int a[3005];
bool mp[3005];
int main()
{
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++ )cin >> a[i];
int count = 0 ;
for(int l = 1 ; l <= n ; l ++ )
{
double sum = 0 ;
for(int i = 0 ; i <= 3000 ; i ++ )mp[i] = 0 ;
// 清空计数 桶
for(int r = l ; r <= n ; r ++ )
{
sum += a[r];
mp[a[r]] = true;
double avg = sum / (r - l + 1);
// cout << avg << endl;
if(avg != int(avg) || mp[int(avg)] == false)continue;
// 假如平均数是小数,或者不存在这个平均数元素,那么不可能合法
count ++ ;
}
}
cout << count << endl;
return 0;
}
这里空空如也
有帮助,赞一个