lsmCC 发表于 2023-11-13 23:33:44

求解,可以说详细一点吗,不是很理解

1
6 1 3
0 3 -2 5 -4 -4
//给定数组a和整数k,q,a有多少个长度至少为k的连续子数组,其中的元素均不超过q
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
      int n,k,q;
      cin>>n>>k>>q;
      vector<int>a(n);
      for(int j=0;j<n;j++)
      {
            cin>>a;
      }
      vector<int>p;
      p.push_back(-1);
      for(int j=0;j<n;j++)//按照q来分割,那么把大于q的位置都找出来,以坐标为分割线,第一次学到
      {
            if(a>q)
            {
                p.push_back(j);
            }
      }
      p.push_back(n);//将小于那部分也包含进去了,也就是没有一个
      int m=p.size();
      long long ans=0;
      for(int j=0;j<m-1;j++) //分成若干个区间
      {
            int d=p-p;
            cout<<d<<endl;
            if(d>=k)
            {
                ans+=(long long )(d-k+1)*(d-k)/2;
            }
      }
      cout<<ans<<endl;

    }
}
/*
这段代码的目的是计算给定数组 a 和整数 k、q 的情况下,有多少个长度至少为 k 的连续子数组,其中的元素均不超过 q。

- 将 -1 存入向量 p 中的目的是确保在后面的循环中,第一个子数组的起始位置正确。因为 -1 不会出现在原始数组 a 中,所以将其作为起始位置。

- 将数组的长度 n 存入向量 p 中的目的是确保最后一个子数组的结束位置正确。将 n 添加到 p 的末尾,表示最后一个子数组的结束位置。

- int d = p - p; 这行代码的目的是计算相邻元素之间的差值,即表示连续子数组的长度。通过计算 p 和 p 的差值,可以得到连续子数组的长度。

- if (d >= k) 这个条件判断是否满足最小长度要求 k。如果满足条件,说明当前连续子数组的长度大于等于 k。

总结一下,将 -1 和 n 存入向量 p 是为了确保第一个子数组和最后一个子数组的起始位置和结束位置正确。而计算 p - p 的差值则是为了得到连续子数组的长度。

希望可以解答您的疑问,如果还有其他问题,请随时提问。*/

5是大于3的那么左边连续子数组长度不是为3,可是d为什么是4呢

isdkz 发表于 2023-11-13 23:33:45

在这段代码中,当计算连续子数组的长度时,使用的是 int d = p - p 这行代码。这行代码的目的是计算相邻元素之间的差值,即表示连续子数组的长度。在给定的例子中,5是大于3的,因此它会被当作一个分割点。所以在这个例子中,p代表的是3,p代表的是5,因此 d = p - p = 5 - 3 = 2 ,而不是4。所以在这个例子中,d应该是2而不是4。希望这能解答您的疑问。

Mike_python小 发表于 2023-11-13 23:35:54

根据代码中的逻辑,变量d表示相邻元素之间的差值,即表示连续子数组的长度。在这段代码中,d的计算方式是通过计算p和p的差值得到的。

在给定的数组a中,如果元素大于q,则将该位置的索引j存入向量p中。而向量p中的元素表示大于q的位置的分割线,用来划分连续子数组。最后,将数组的长度n也加入到向量p的末尾,表示最后一个子数组的结束位置。

所以,对于给定的数组和元素不超过3的条件,根据代码中的逻辑,向量p的值为[-1, 1, 3, 6]。其中,p-p表示第一个子数组的长度,为1-(-1)=2;p-p表示第二个子数组的长度,为3-1=2;p-p表示第三个子数组的长度,为6-3=3。

所以,对于这个数组,d的计算结果为。其中,第一个d=2表示左边连续子数组的长度为2,并不满足长度至少为k的要求。因此,前面的输出结果为2。

希望以上解释能够帮助您理解代码的逻辑。如果还有其他问题,请随时提问。
页: [1]
查看完整版本: 求解,可以说详细一点吗,不是很理解