蓝桥杯历届试题-连号区间数

暴力思路：

    首先这个题需要理解这个连续性是什么，比如给你一个数组：1 3 5 4 2，然后我在里面随便去一段（取3 5 4）然后我把它排序（从小到大）发现也是3，4，5        那   就说明是连续的，除此之外当l=r时也算作连续

    分别枚举区间的左端点和右端点，对左右端点区间进行sort排序，判断是否连续

   暴力做法时间复杂度O(n^3logn)大于O(n^2)，所以只能过一部分的数据，但能得一部分得分数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>


using namespace std;
using ll=long long;

const int N=5e4+10;

int a[N],bac[N];
int res;
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  for(int i=1;i<=n;i++)//枚举左右端点i，j，判断是否连续
  {
    for(int j=i;j<=n;j++)
    {
      memcpy(bac,a,sizeof a);// 这里要把数组的初始状态存在bac数组中，因为每次sort排序后，数组的顺序会发生改变。
      sort(a+i,a+j+1);
      bool flag=true;
      for(int k=i;k<j;k++)
      {
        if(a[k+1]-a[k]>1)
        {
          flag=false;
          break;
        }
      }
      if(flag)res++;
      memcpy(a,bac,sizeof bac);// 还原数组a的初始状态
    }
  }
  cout<<res;
  return 0;
}

对暴力做法进行优化，我们假设区间[a,b],则在区间[a,b]之间一共有b-a+1个数，由此说明在区间[a,b]中的

最大值和最小值之间就相差了b-a。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>


using namespace std;

// 定义常量N为5e4+10（50010），作为数组大小的上限。定义常量INF为1e8（100000000），用作无穷大的值。
const int N = 5e4 + 10, INF = 1e8;

int a[N], bac[N]; // 定义数组a用来存储输入的序列，bac数组定义了但未在代码中使用
int res; // 定义变量res用来统计满足条件的子序列数量

int main() {
// 加速输入输出。禁用C与C++的同步以及手动绑定cin与cout
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n; // 定义n用来接收序列的长度
cin >> n; // 输入序列的长度n
for (int i = 1; i <= n; i++) {
cin >> a[i]; // 循环接收序列的每个值
}

// 双重循环检查所有的(i, j)对，其中i为子序列的起始位置，j为子序列的结束位置
for (int i = 1; i <= n; i++) {
int maxb = -INF, mina = INF; // 初始化当前子序列的最大值和最小值
for (int j = i; j <= n; j++) {
maxb = max(maxb, a[j]); // 更新当前子序列的最大值
mina = min(mina, a[j]); // 更新当前子序列的最小值
// 如果当前子序列的最大值与最小值之差等于子序列的长度差，则找到了一个符合条件的子序列
if (maxb - mina == j - i) res++;
}
}
cout << res; // 输出满足条件的子序列总数
return 0;
}