蓝桥杯 - [历届试题]连号区间数(暴力)
发布日期:2021-07-01 00:18:29
浏览次数:2
分类:技术文章
本文共 838 字,大约阅读时间需要 2 分钟。
题目链接:
时间限制:1.0s 内存限制:256.0MB问题描述
小明这些天一直在思考这样一个奇怪而有趣的问题:
在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 5 3 4 2 5 1
样例输出
7
9
解题思路
数据比较水,直接暴力判断就行了。
#includeusing namespace std;int a[50005];int main() { int n, max_, min_, ans = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { min_ = max_ = a[i]; for (int j = i; j < n; j++) { min_ = min(min_, a[j]); max_ = max(max_, a[j]); if (max_ - min_ == j - i) ans++; } } printf("%d\n", ans); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/90318959 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月23日 05时17分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
如何在SpringMVC中配置Atomikos分布式事务
2019-05-01
Spring Boot 注解@EnableAutoConfiguration的解析
2019-05-01
SpringApplication执行流程
2019-05-01
Spring Boot Quartz 动态任务实现方式
2019-05-01
Spring MVC Quartz 动态任务实现方式
2019-05-01
自定义Starter
2019-05-01
Spring Batch 入门之 CSV-to-DB
2019-05-01
日志写入数据库:Log4j2-JDBCAppender
2019-05-01
分布式事务原理探究(一)
2019-05-01
MySQL 中基于 XA 实现的分布式事务-学习记录
2019-05-01
Java 并发学习记录之线程间通信
2019-05-01
Java并发学习记录之volatile
2019-05-01
Spring Security Oauth2 如何增加自定义授权模式
2019-05-01
spring cloud consul 应用的多实例名的解决
2019-05-01
linux系统编程之信号(五):实时信号与sigqueue函数
2019-05-01
225. 用队列实现栈
2019-05-01
linux系统编程之信号(六):竞态条件与sigsuspend函数
2019-05-01
124. 二叉树中的最大路径和
2019-05-01
LeetCode 148:排序链表 【归并】
2019-05-01