2019牛客暑期多校训练营(第一场)A Equivalent Prefixes
2024-08-31 08:21:16
题意:
先输入一个n,代表两个数组里面都有n个数,然后让你从中找到一个p<=n,使其满足(1<=l<=r<=p<=n)可以让在(l,r)这个区间内在两个数组中的的最小值的下标一样
题解:
我一直认为区间起点l一直是1,突然发现他还可以变T_T
p为1肯定对着咧
当p大于1的时候,我们只需要判断两个数组中的每一个位置在左边遇见的第一个最小值的位置是相同的,一直找到不相同的位置,那个位置就是最大的p,那么这样的话就可以通过小区间的最小值位置相同依次证明大区间的最小值位置相同
假设我们证明(1,4)区间最小值位置
前提条件(3,4)最小值位置在3,(1,3)最小值位置相同
解:
那么从(3,4)这个区间找到最小值位置是3,又因为两个区间在(1,3)最小值位置相同,所以整个(1,4)区间最小值位置都相同
代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<queue>
5 #include<algorithm>
6 #include<vector>
7 #include<stack>
8 using namespace std;
9 const int maxn=1e5+10;
10 int a[maxn],b[maxn],la[maxn],lb[maxn];
11 stack<int>sa,sb;
12 int main()
13 {
14 int n;
15 while(~scanf("%d",&n))
16 {
17 for(int i=1; i<=n; ++i)
18 {
19 scanf("%d",&a[i]);
20 }
21 for(int i=1; i<=n; ++i)
22 {
23 scanf("%d",&b[i]);
24 }
25 while(!sa.empty()) sa.pop();
26 for(int i=1;i<=n;++i)
27 {
28 while(!sa.empty() && a[i]<a[sa.top()]) sa.pop();
29 if(sa.empty()) la[i]=0;
30 else la[i]=sa.top(); //找的是左边第一个小于它的数
31 sa.push(i); //如果靠着他的左边那个数不小于它,那大于左边那个数的数也不可取
32 }
33 while(!sb.empty()) sb.pop();
34 for(int i=1;i<=n;++i)
35 {
36 while(!sb.empty() && b[i]<b[sb.top()]) sb.pop();
37 if(sb.empty()) lb[i]=0;
38 else lb[i]=sb.top();
39 sb.push(i);
40 }
41 int ans=1;
42 for(int i=2;i<=n;++i)
43 {
44 if(la[i]==lb[i]) ans=i;
45 else break;
46 }
47 printf("%d\n",ans);
48 }
49 return 0;
50 }
最新文章
- JS限制input输入的为数字并且有小数的时候最多保留两位小数
- SQL Server 2008连接字符串写法大全
- osg设置相机参数,包括初始位置
- C\C++ 框架和库整理(转)
- Arduino 电平转换 升压 OUTPUT与9V/12V元件通信
- PHP实现无级递归分类(ThinkPHP框架)
- hdu 3966 树链剖分
- jsp与servlet之间的参数传递【转】
- WordPress 全方位优化指南(上)
- 提高IIS的并发量
- Ubuntu 13.10 Rhythmbox 播放器不能播放MP3。安装插件
- wp7学习笔记
- adb和机顶盒一些常识
- C# --- ??(空接合操作符)的一个案例
- Android开发之漫漫长途 XIX——HTTP
- 学习windows编程 day3 之滚动条完善
- Oracle 修改字段顺序的两种方法
- 破解X-Pack和更新许可证
- 利率计算v4.0--测试--软件工程
- 【BZOJ】4558: [JLoi2016]方
热门文章
- 白日梦的Elasticsearch笔记(一)基础篇
- .NET 云原生架构师训练营(模块二 基础巩固 RabbitMQ Masstransit 异常处理)--学习笔记
- 【Spring】Spring JdbcTemplate
- 一条查询SQl是怎样执行的
- 十三:SQL注入之MYSQL注入
- python常见题型
- 虚拟机Linux安装Oracle容器并实现局域网其他主机访问查询
- Over Permission - Pikachu
- [Usaco2007 Jan]Balanced Lineup 飞盘比赛
- 2V升3.3V芯片,输出500MA,低功耗10uA解决方案