Codeforces 251A（求升序数组任意三个数中里最大差值不超过k的方案数）

STL

题面链接

• 题意

  求升序数组任意三个数中里最大差值不超过k的方案数

• 输入

  n,d (1 ≤ n ≤ $10^5$; 1 ≤ d ≤ $10^9$).
  接下来n个输入代表n个数

• 输出

  输出满足条件的最长长度ans

• 样例

  input
  4 3
  1 2 3 4
  output
  4
  input
  4 2
  -3 -2 -1 0
  output
  2
  input
  5 19
  1 10 20 30 50
  output
  1

• 代码

#include<stdio.h>
#include<queue>///一定要包含这个头文件
#include<string>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int a[100010];
int main()
{
    int n,i,j,x;
    while(~scanf("%d%d",&n,&x))
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        queue<int>q;///队列是先进先出
        long long cnt=0,ans=0;
        for(i=0;i<n;i++)
        {
            q.push(a[i]);
            cnt++;
            while((q.back()-q.front())>x)///q.front()是最先输入的那个，是在栈底的元素
            {
                q.pop();
                cnt--;
            }
            ans+=((cnt-1)*(cnt-2)/2);///目前进入的一定是要选的
        }
        cout<<ans<<endl;
    }
   return 0;
}