列车调度C语言数据结构,数据结构——列车调度

大家好，又见面了，我是你们的朋友全栈君。

题目链接：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.cn/159388.html原文链接：https://javaforall.cn