文档章节

连号区间 蓝桥杯 算法

f
 florida姣
发布于 2014/05/23 00:55
字数 422
阅读 16
收藏 0
 /*
小明这些天一直在思考这样一个奇怪而有趣的问题*
在1~N的某个全排列中有多少连号区呢?这里所说的连号区间的定义是:
 如果区间【L,R】里的所有元素(即此排列的第L个到第R个元素) 
 递增排序后能得到一个长度为R-L+1的“连续”数列,责成这个区间为连号区间 
 当N很小的时候,小明可以很快的算出答案,但是当N变大的时候,问题就不是那么简单了
 现在小明需要你的帮忙。 
  
  输入格式:
  第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。
  第二行是N个不同的数字Pi(1 <= Pi <= N), 表示这N个数字的某一全排列。
 输出格式
  输出一个整数,表示不同连号区间的数目。
 样例输入1
  4
  3 2 4 1
 样例输出1
  7
 样例输入2
  5
  3 4 2 5 1
 样例输出2
  9
   
*/
# include <stdio.h>
int  main()
{
 int num[50010];
 int n,sum,min,max;
 scanf("%d",&n);
 for(int i=0; i<n; i++)
 {
  scanf("%d",&num[i]);
 }
 sum+=n;       //单个数据也是连续区间,因为它自己也算 
 for(int i=0;i<n;i++)
 {
  max=min=num[i];
  for(int j=i+1;j<n;j++)
   {
    if(num[j]>max)
    max=num[j];
    if(num[j]<min)
    min=num[j];
    if(max-min==j-i)   //最大数据和最小数据差刚好也是下标之差,说明它们是一组可以连续的数据,也就是所谓的连续区间 
    sum++;
   }
 }
 printf("%d\n",sum);
 return 0;
 
}
/*
7
1 3 6 5 4 7 2
15
*/

© 著作权归作者所有

f
粉丝 0
博文 1
码字总数 422
作品 0
西安
私信 提问
蓝桥杯第七届_快速排序

原文: 快速排序 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素...

Big_laoshu
2017/11/20
0
0
我算不算一个程序员

小弟目前大二,主要学习C#(但是我不太喜欢,所以就学的一般),根据学校安排的课程的话最多学完基础,我个人喜欢PHP,从开始学习到目前大约3个月,能够进行基础模块的制作(BBS,在线聊天室...

我是一只小小鸟001
2017/03/21
286
3
蓝桥杯 第七届省赛--快速排序

快速排序 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小...

xnh_565175944
2018/03/30
0
0
蓝桥杯,你怎么看???

蓝桥杯又要报名了,各位大boss们怎么看待蓝桥杯~~~

嘚瑟的小孩
2016/11/29
571
7
【蓝桥杯】2019第十届蓝桥杯B组C++年号字串

小明用字母A 对应数字1,B 对应2,以此类推,用Z 对应26。对于27 以上的数字,小明用两位或更长位的字符串来对应,例如AA 对应27,AB 对 应28,AZ 对应52,LQ 对应329。 请问2019 对应的字符...

Debug客栈
03/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
6
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
7
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
5
0
OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
今天
1K
11
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合(类似mysql 中的 表): 后面我们大部分都...

TcWong
今天
40
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部