Greedy Sequence

Greedy Sequence

题意：

• 给你一个长度为序列,然后输出个序列的最大长度,每个序列的第个数都是,后面的数必须满足并且后面的数都应该在序列中寻找。而数组表示的是数组中每个数的下标，在序列中相邻数在序列中的下标不能超过
  每个元素的下一个元素一定是与他距离不超过 k 的所有元素中，权值最大 的元素。
  样例2：
  1
  2
  3 1
  4 3 1
  5 2
  6 5 2
  7 5 2

思路：

• 因为个序列,每个序列的第一个数字都是,那么只要找出数字在序列的对应下标，然后再找出再序列中的下标，比较两者下标的差的绝对值是否小于等于，那么假如小于，那么序列的长度等于序列的长度加1，否则找出再序列中的下标重复操作找出序列的长度

#include <bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int a[M];
int n,x,k;
int ans[M];
int main( )
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            a[x]=i;//每个数出现的下标
        }
        for(int i=1;i<=n;i++)
        {
            ans[i]=1;
            for(int j=i-1;j>=1;j--)//寻找下一个从大到小寻找
            {
                if(abs(a[j]-a[i])<=k)
                {
                    ans[i]=ans[j]+1;
                    break;
                }
            }
            printf("%d%c",ans[i],i==n?' ':'\n');
        }
    }
    return 0;
}

• 用预处理找出每个下标在~比小的最大值存入数组。
• 输出时，每个序列的第位是，在序列中找到对应的,从当前位置开始查找满足序列的最长长度，于是数组就找出了在下标~中比小的最大值。序列中每个数的下一位都是比它小的最大值。所以

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int a[M],pre[M];
int ans[M];
int main( )
{
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        set<int>s;
        int l=1,r=min(k+1,n);//保证开始set中有k+1个数，set中最大的数的下标比最小数的下标差值绝对值为k
        for(int i=l;i<=r;i++)
        {
            s.insert(a[i]);//从小到大排序
        }
        for(int i=1;i<=n;i++)
        {
            while(r-i<k&&r+1<=n)//保证i的右边最少有k个数
            {
                s.insert(a[++r]);
            }
            while(i-l>k)//保证i的左边最多k个数
            {
                s.erase(a[l++]);
            }
            set<int>::iterator it=s.lower_bound(a[i]);//找出第一个比a[i]大于或等于数的定位器
            if(it==s.begin( ))//范围内没有比自己小的数
            {
                pre[a[i]]=0;
            }
            else
            {
                pre[a[i]]=*(--it);//大于等于a[i],a[i]已经在set中所以返回的是a[i]的定位器，找出最大的比a[i]的数就是a[i]的前一位,所以是*(--it);
            }
        }
        ans[0]=0;
        for(int i=1;i<=n;i++)
        {
            ans[i]=ans[pre[i]]+1;
            printf("%d%c",ans[i],i!=n?' ':'\n');
        }
    }
    return 0;
}