题解：CF1270B Interesting Subarray

题意

t

组数据。

给你一个包含

n

个正整数的序列

a

，你需要从中找到一个连续子序列，使得这个连续子序列的最大值减最小值的差大于等于这个连续子序列的元素个数。如果能找到，还要输出一种构造方案。

分析

明显发现，如果这个序列所有长度为

2

的连续子序列都不符合要求，那么答案显然无解，反之有解。

那么问题来了，为什么长度为

1

，长度为

3

，或者更长的不行呢？

我们一个一个看。

如果长度为 $1$ ，那么最大值和最小值均为本身，那么最大值减最小值为 $0$ ，不符合要求。
如果长度为 $3$ 或者更大，我们发现，他的存在是基于长度为 $2$ 的连续子序列不存在的情况下而诞生的，但是我们发现，如果长度为 $2$ 的连续子序列都找不到，那么长度为 $3$ 的连续子序列就更找不到了，更何况更大的呢。因为你没有任何一种情况满足长度为 $2$ 的子序列不符合要求，但是长度为 $3$ 的子序列却符合要求了。所以不符合要求。

总结

综上所述，如果说长度为

2

的连续子序列没有符合情况的，那么就无解，否则输出这两个数的位置即可。

代码

CPP

//By xiaozhou001
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int t,n,a[N],flag;
int main()
{
    ios::sync_with_stdio(false);//解除cin/cout的流绑定
    cin>>t;
    while(t--){
        flag=1;//一定要注意多测清空
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];//我是输入
        for(int i=1;i<n;i++)
            if(abs(a[i]-a[i+1])>=2){//我是判断
                cout<<"YES"<<endl<<i<<" "<<i+1<<endl;//输出有解情况
                flag=0;//代表已经找到了一组解
                break;//一种情况就够了，SPJ会帮你扫清一切障碍
            }
        if(flag)cout<<"NO"<<endl;//无解
    }
    return 0;
}

题解：CF1270B Interesting Subarray

文章操作

题意

分析

总结

代码

相关推荐

评论

题解：CF1270B Interesting Subarray