Ubuntu LVS 细胞因子 机器学习 Java开发手册 人工智能 智慧树 Seajs vue路由 admin框架 郑州网络 android实战项目 android经典项目开发实战 android项目实例 jq触发点击事件 oracle分页关键字 oracle取第一条数据 mysql修改字段值 java上传图片 matlab取实部 kubernetes视频 java斐波那契数列 java基础编程 java中class java获取 mac地址修改器 千元以下最好的手机 忧思华光玉攻略 js删除节点 msdev 深入浅出通信原理 ps怎么插入表格 cms教程 电子书制作软件 js包含字符串 苹果放大镜 语音分析软件 vscode全局搜索 疯狂的站长 win7仿win8主题
当前位置: 首页 > 学习教程  > 编程语言

蓝桥杯真题-连号区间数

2021/2/13 18:31:18 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述 小明这些天一直在思考这样一个奇怪而有趣的问题: 在1~N的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是: 如果区间[L, R] 里的所有元素(即此排列的第L个到第R个元素)递增排序后能得到一个长度…

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题:
在1~N的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是:
如果区间[L, R] 里的所有元素(即此排列的第L个到第R个元素)递增排序后能得到一个长度为R-L+1的“连续”数列,则称这个区间连号区间。
当N很小的时候,小明可以很快地算出答案,但是当N变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入

第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。
第二行是N个不同的数字Pi(1 <= Pi <= N), 表示这N个数字的某一全排列。

输出

输出一个整数,表示不同连号区间的数目。

样例输入

4
3 2 4 1

样例输出

7

代码如下:

#include <iostream>
using namespace std;
const int N = 10010, INF = 100000000;
int a[N], n;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		int mins = INF, maxs = -INF;
		for (int j = i; j < n; j++) {
			mins = min(mins, a[j]);
			maxs = max(maxs, a[j]);
			if (maxs - mins == j - i) {
				res++;
			}
		}
	}
	cout << res << endl;


	return 0;
}

本文链接: http://www.dtmao.cc/news_show_700261.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?