[已解决]没有看懂代码是怎么实现的

lsmCC

1. //给定数组a和整数k，q,a有多少个长度至少为k的连续子数组，其中的元素均不超过q
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.     int t;
   
7.     cin>>t;
   
8.     while(t--)
   
9.     {
   
10.         int n,k,q;
    
11.         cin>>n>>k>>q;
    
12.         vector<int>a(n);
    
13.         for(int j=0;j<n;j++)
    
14.         {
    
15.             cin>>a[j];
    
16.         }
    
17.         vector<int>p;
    
18.         p.push_back(-1);
    
19.         for(int j=0;j<n;j++)  //按照q来分割，那么把大于q的位置都找出来
    
20.         {
    
21.             if(a[j]>q)
    
22.             {
    
23.                 p.push_back(j);
    
24.             }
    
25.         }
    
26.         p.push_back(n);
    
27.         int m=p.size();
    
28.         long long ans=0;
    
29.         for(int j=0;j<m-1;j++)
    
30.         {
    
31.             int d=p[j+1]-p[j];
    
32.             if(d>=k)
    
33.             {
    
34.                 ans+=(long long )(d-k+1)*(d-k)/2;
    
35.             }
    
36.         }
    
37.         cout<<ans<<endl;
    
38. 
    
39.     }
    
40. }

复制代码

为什么要把-1和n存入p容器,还有 int d=p[j+1]-p[j]，为什么要这样写呢

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-11-13 22:06:45

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

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

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

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

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

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

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

跳转到最佳答案楼层

isdkz

将-1和n存入p容器是为了标记数组a的起始和结束位置。在这个问题中，我们需要找到数组a中所有长度至少为k的连续子数组，其中的元素均不超过q。因此，我们需要标记数组a的起始和结束位置，以便在计算连续子数组长度时考虑边界情况。

而 int d=p[j+1]-p[j] 的目的是计算相邻两个分割点之间的距离，即当前分割点和下一个分割点之间的元素个数。这个距离d代表了当前分割点和下一个分割点之间的连续子数组长度。

在这段代码中，我们使用了p容器来存储所有大于q的元素的位置，以便后续计算满足条件的连续子数组个数。

Mike_python小

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

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

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

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

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

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

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