hdu 6860 Fluctuation Limit 双向贪心

题意：

给你n个区间[li,ri]，和一个整数k，你从每一个区间内选出来一个数，把从第i个区间内选出来数放在第i个位置，这样会构成一个长度为n的序列，你需要保证序列中任意两个相邻的数之差的绝对值要小于等于k

如果这样的序列存在就输出Yes和序列，否认输出No

题解：

就是前后两次贪心就可以了

先说一下从前向后贪心，我们设我们选择的第i个数就是v[i]

因为前一个数的选择会影响到后一个数的选择，所以我们需要进行从前向后贪心

L[i+1]=max(L[i+1],L[i]-k)

R[i+1]=min(R[i+1],R[i]+k)

然后从后到前在进行一边这样的贪心，因为后面的数也会影响前面的数

L[i]=max(L[i],L[i+1]-k)

R[i]=min(R[i],R[i+1]+k)

这样的话会得到一个新的li和ri数组，我们只需要输出其中任意一个元素就行

就是如果第一个区间[L[1],R[1]]输出第L[1],那么第二个区间也就输出L[2]

不要第一个区间输出L[1]，第二个区间输出R[2]，要输出就输出对等位置的元素

代码：

#include<stack>

#include<queue>

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fi first

#define se second

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

const int mod=1e9+7;

const double eps=1e-8;

int a[maxn],b[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,k;

        scanf("%d%d",&n,&k);

        for(int i=1;i<=n;++i)

        {

            scanf("%d%d",&a[i],&b[i]);

        }

        for(int i=2;i<=n;++i)

        {

            a[i]=max(a[i-1]-k,a[i]);

            b[i]=min(b[i-1]+k,b[i]);

        }

        for(int i=n-1;i>=1;--i)

        {

            a[i]=max(a[i+1]-k,a[i]);

            b[i]=min(b[i+1]+k,b[i]);

        }

        int flag=0;

        for(int i=1;i<=n;++i)

        {

            if(a[i]>b[i])

            {

                flag=1;

                break;

            }

        }

        if(flag)

        {

            printf("NO\n");

        }

        else

        {

            printf("YES\n");

            for(int i=1;i<=n;++i)

            if(i==n)

                printf("%d\n",a[i]);

            else printf("%d ",a[i]);

        }

    }

    return 0;

}

巴特西

hdu 6860 Fluctuation Limit 双向贪心

最新文章

热门文章