大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
题目链接：https://pintia.cn/problem-sets/1045870129681440768/problems/1045870197130047495#p-2
题目大意：给你一列火车，上面有表号，问给你几个火车隧道，能使车厢从大到小。
一道有思维结构的模拟题。
先说一下核心解体思想：就是一个序列里，有多少个从大到小排好序的序列，求个数。
朴素的模拟思想，先读入一个数组，从头到尾判断，含有多少个，从大到小的序列，用used数组标记使用，但是这种做法会超时。
这里先给出错误代码：
#include
using namespace std;
const int INF=1e6+10;
const int maxn=100000+10;
int a[maxn];
int main()
{
int n; scanf(“%d”,&n);
for(int i=0;i
int num=n,exnum=0;
while(num>0)
{
bool flag=true;
int t;
for(int i=0;i
{
if(a[i]!=INF)
{
if(flag)
{
num–;
exnum++;
t=a[i];
a[i]=INF;
flag=false;
}
else if(a[i]
{
t=a[i];
a[i]=INF;
num–;
}
}
}
}
printf(“%d\n”,exnum);
return 0;
}
超时之后开始简化自己的思想，再网上看到了二分思想A题，但总感觉还有更为简单的方法。
想来想去最后使用的，使用数组储存最一个隧道末尾数字的大小+二分；
下面给出AC代码，代码下面有一些具体解释：
#include
using namespace std;
const int INF=1e6+10;
const int maxn=100000+10;
int a[maxn];
int main()
{
int n; scanf(“%d”,&n);
int len=1;
for(int i=0;i
{
int t; scanf(“%d”,&t);
if(i==0) a[0]=t;
else
{
if(t>a[len-1])
{
a[len++]=t;
}
else
{
int pos=lower_bound(a,a+len,t)-a;
//cout<
a[pos]=t;
}
//sort(a,a+len);
}
}
printf(“%d\n”,len);
return 0;
}
可能会有疑问，lower_bound二分函数，只有在数组排好序的时候才能使用，但是代码中的排序函数是被注释掉的，而且去掉注释会超时，但是仔细想想就会知道，我们用来每次更新火车隧道末尾数字的时候，总是选择的跟他的值差距最小的(因为lower_bound函数总是找到的是第一个值)，这个过程中可以保证数组是从小到大排好的，从而省略掉了排序的函数。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/159388.html原文链接：https://javaforall.net
![数据结构——线索化二叉树和哈夫曼树[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
