首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7498

火车站的列车调度铁轨的结构如下图所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任…

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有 9 趟列车,在入口处按照 { 8,4,2,5,3,9,1,6,7 } 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?

时间限制:5000

内存限制:65536

输入

输入第一行给出一个整数 N (2 ≤ N ≤ 105),下一行给出从 1 到 N的整数序号的一个重排列。数字间以空格分隔。

输出

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。


样例输入

9
8 4 2 5 3 9 1 6 7

样例输出

4
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 // #include <iostream> #include <bits/stdc++.h> using namespace std; int main() {     int n;     cin >> n;     int a[n] = {0};     int x;//每次输入的列车序号     int t = 0;     for (int i = 0; i < n; i++)     {         cin >> x;         if (t == 0 || a[t - 1] < x) //t-1是因为a[t]是0,a[t-1]才是真正的序号         //如果最后一个道路的最后一个元素都比x小,         //说明前几条道路也没有能容下x的了         {             a[t] = x; //第一个进去的,一定是这一列最大的             // printf("t=%d  a[%d]=%d  x=%d\n",t,i,a[i],x);             t++;         }         int l = 0, r = t, mid; //t代表了当前开辟的道路的数量         while (l < r)         {             mid = (r - l) / 2 + l;             if (x <= a[mid])             {                 r = mid;             }             else                 l = mid+1 ;         }         a[l] = x;         //测试用:         // for (int j = 0; j < t; j++)         // {         //     cout << a[j] << ' ';         // }         // cout << endl;     }     cout << t;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include<iostream>  using namespace std; int main(){ int n;cin>>n; int a[n];//a[i]存放的是这条道上的火车中最小的编号。  int max = 0; int k; while(n--){ cin>>k; if(max == 0 || a[max-1] < k){//当道为零或者或者所有道的最小号都小于新来的号码,需要加一条道来放这个号码  a[max++] = k; } else{//有道能放下新来的,找到比新来的大且和间距最小的那个道,用新来的覆盖它的号码 ,二分查找  int l=0;int r=max-1; while(l<r) { int mid=l+(r-l)/2; if(a[mid]>k) { r=mid-1; } else { l=mid+1; } } a[l]=k; } } cout<<max; return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码3 #include<bits/stdc++.h> using namespace std; const int N=100005; int a[N],cnt,n; int find(int x) { if(cnt==0)return 0; int l=0,r=cnt-1;     while(l<r)     {      int mid=l+r>>1;      if(a[mid]>x)r=mid;      else l=mid+1;     }     if(a[r]>x)return r; return cnt; } int main() { cin>>n; for(int i=0;i<n;++i) { int x;cin>>x; int t=find(x); if(t==cnt)a[cnt++]=x; else a[t]=x; } cout<<cnt; return 0; }</pre>
这道题暂未补解析。