1553: Good subsequence （很奇妙的set模拟题，也可以直接暴力）

开发者恩希技术 2022年11月21日

0 收藏 672 点赞 3,262 浏览 1535 个字

1553: Good subsequence

Summary Time Limit: 2 Sec Memory Limit: 256 Mb Submitted: 895 Solved: 335

Description

Give you a sequence of n numbers, and a number k you should find the max length of Good subsequence. Good subsequence is a continuous subsequence of the given sequence and its maximum value – minimum value<=k. For example n=5, k=2, the sequence ={5, 4, 2, 3, 1}. The answer is 3, the good subsequence are {4, 2, 3} or {2, 3, 1}.

Input

There are several test cases.
Each test case contains two line. the first line are two numbers indicates n and k (1<=n<=10,000, 1<=k<=1,000,000,000). The second line give the sequence of n numbers a[i] (1<=i<=n, 1<=a[i]<=1,000,000,000).
The input will finish with the end of file.

Output

For each the case, output one integer indicates the answer.

Sample Input

Sample Output

3
1

Hint

Source

给你一个序列，长度为n
然后给一个数字k
问你符合要求的子段的最大长度是多少？
符合要求的子段：子段的最大值和最小值的差小于等于k分析：
利用set模拟该过程，或者直接暴力
不知道怎么描述这个过程
不过按照代码模拟一下样例1应该就明白了

#include<cstdio>
#include<string>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<cctype>
#include<stack>
#include<sstream>
#include<list>
#include<assert.h>
#include<bitset>
#include<numeric>
#define max_v 10005
using namespace std;
int a[max_v];
set<int> s;
int main()
{
    int n,k;
    while(~scanf("%d %d",&n,&k))
    {
        s.clear();
        for(int i=;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int j=;
        int ans=;
        for(int i=;i<=n;i++)
        {
            s.insert(a[i]);
            if(*s.rbegin()-*s.begin()>k)
            {
                s.erase(s.find(a[j]));
                j++;
            }
            ans=max(ans,i-j+);
        }
        printf("%d\n",ans);
    }
    return ;
}
/*
给你一个序列，长度为n
然后给一个数字k
问你符合要求的子段的最大长度是多少？
符合要求的子段：子段的最大值和最小值的差小于等于k分析：
利用set模拟该过程，或者直接暴力
不知道怎么描述这个过程
不过按照代码模拟一下样例1应该就明白了
*/