精华内容
下载资源
问答
  • 列车调度

    2019-09-24 13:41:57
    火车站的列车调度铁轨的结构如下所示。 Figure 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟...

    列车调度

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


    Figure

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

    输入格式:

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

    输出格式:

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

    输入样例:
    9
    8 4 2 5 3 9 1 6 7
    
    输出样例:
    4
    代码如下:
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a[100000]={-1};
    int b[100000]={0};
    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
     cin>>a[i];
    int t=0;
    int k=1;
    int t1=0;
    for(int i=2;i<=n;i++)
    {
    if(a[i]>=a[t1] && a[i]<=a[k] && a[k]>=a[i])
      k=i;
    if(a[i]>a[k])
    {           
         t1=k;
         k=i;  
         b[t++]=a[t1];        
    }
    }
    if(a[k]>b[t-1])
      b[t]=a[k];
    int sum=0;
    if(b[t]==0)
    t=t-1;
    for(int i=0;i<=t;i++)
       sum++; 
     cout<<sum<<endl;
    return 0;
    }
    我的思路:
    
    正的看就是,可以看成区间段,属于一个最大的区间段,以题目例子解释下代码!
    
    先是这个:8 4 2 5 3 9 1 6 7
    
    第一次结果: 第一段 8 4 2,5 3 9 1 6 7
    
    第二次结果:第二段 5 3,9 1 6 7
    
    第三次结果: 第三段:9 1 ,6,7;
    
    第四次结果: 第四段:6。
    
    第五次结果:第五段:7;
    
    8 4 2
    
    5 3
    
    9 1
    
    6
    
    7
    
    大家会问怎么会有五条,我在这里要解释一下,本来存在一条路,求得是用于调度的平行道路,需要多少?
    
    这是后面往前面看。
    
    从前面看的也可以去依次推敲,代码稍微改动。



    
                

    转载于:https://www.cnblogs.com/new-zjw/p/8541043.html

    展开全文
  • 火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在入口处...

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

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

    输入格式:

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

    输出格式:

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

    输入样例:

    9

    8 4 2 5 3 9 1 6 7

    输出样例:

    4

    样例说明:

    第一条轨道:1 2 4 8

    第二条轨道:3 5

    第三条轨道:6 9

    第四条轨道:7 数组长度表示轨道数,火车进站类似于进栈,当轨道里只有一辆车的时候,栈顶即为这辆车,以后还有火车进入轨道,如果火车的编号比任意轨道的栈顶还要大,就新增一条轨道,否则每次从后边来的火车里找到第一个大于栈顶的轨道进入。

    数据较大,采用二分查找。

    #include using namespace std;

    const int maxn = 1e5 + 5;

    int main(){

    int n;

    cin >> n;

    int a[maxn];

    int len = 0;

    for (int i = 0; i < n;i++){

    int x;

    cin >> x;

    if(len==0||a[len-1]> 1;

    if(a[mid]>x)

    r = mid;

    else

    l = mid + 1;

    }

    a[l] = x;

    }

    }

    cout << len << endl;

    //system("pause");

    return 0;

    }

    展开全文
  • 71 列车调度

    2019-03-24 12:31:42
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...

    7-10 列车调度 (25 分)

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

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

    输入格式:

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

    输出格式:

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

    输入样例:

    9
    8 4 2 5 3 9 1 6 7
    

    输出样例:

    4

    #include<iostream>
    #include<set>
    #include<bits/stdc++.h>
    using namespace std;
    set<int> v;
    //集合中放的是每一个车道的最后一个车的车号;
    int main(){
        int n,x;
        scanf("%d %d",&n,&x);
        v.insert(x);
        for(int i=1;i<n;i++){
            scanf("%d",&x);
            if(x<*v.rbegin()){
                v.erase(v.upper_bound(x));//大于x的第一个的下标
              //lower_bound---小于等于x的第一个数字的下标;
            }//如果在前面的多个车道上,车道上的最后的一辆车的尾号比当前的大,这辆车就可以放到上面去
            //不用占车道,并且是放到两个车号的差距最小的车道上;
            v.insert(x);
        }
        //v中放的是所有车道的最后一辆车的车号·;输出
    //    set<int> :: iterator it= v.begin();
    //    set<int> :: iterator id = v.end();
    //    while(it!=id){
    //        cout<<*it<<" ";
    //        it++;
    //    }
        printf("%d\n",v.size()) ;
        return 0;
    }
    
    

     

    展开全文
  • PAT列车调度

    2017-03-27 21:15:08
    L2-014. 列车调度 时间限制 300 ms 内存限制 65536 kB ...火车站的列车调度铁轨的结构如下所示。 Figure 两端分别是一条入口(Entrance)轨道和一条出口(Exit

    L2-014. 列车调度

    时间限制
    300 ms
    内存限制
    65536 kB
    代码长度限制
    8000 B
    判题程序
    Standard
    作者
    陈越

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


    Figure

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

    输入格式:

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

    输出格式:

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

    输入样例:
    9
    8 4 2 5 3 9 1 6 7
    
    输出样例:
    4
    https://www.patest.cn/contests/gplt/L2-014

    题意 就是 小的数字跟在大数后面 看有几组 跟杭电的最少拦截系统一样

    一写就超时了 没看数据10万的(做题时间复杂度还是写代码前最需要考虑的)

    超时的代码

    #include<bits/stdc++.h>
    using namespace std;
    
    int aa[100010];
    bool vis[100010];
    
    int main()
    {   int n,i,xf,j;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0; i<n; i++)
                scanf("%d",&aa[i]);
            memset(vis,0,sizeof(vis));
            int sum=0;
            for(i=0; i<n; i++)
            {
                if(vis[i]) continue;
                xf=aa[i];
                vis[i]=1;
                for(j=i+1; j<n; j++)
                {
                    if(aa[j]<xf&&!vis[j])
                    {
                        xf=aa[j];
                        vis[j]=1;
                    }
    
                }  
                sum++;
            }
            printf("%d\n",sum);
        }
        return 0;
    }

    10万的吗  不是O(N)就是O(N*LOGN)的 还有其他的吗?

    #include<bits/stdc++.h>
    using namespace std;
    set<int>ss;
    int aa[100010];
    
    int main()
    {
        int n,i,xf,j;
        set<int>::iterator it;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0; i<n; i++)
                scanf("%d",&aa[i]);
            ss.clear();
            ss.insert(100010);
            int sum=0;
            for(i=0; i<n; i++)
            {
                it=ss.upper_bound(aa[i]);
                if(it==ss.end())
                {
                    ss.insert(aa[i]);
                }
                else
                {
                    ss.erase(it);//删除的时候迭代器it会被删除
                    ss.insert(aa[i]);
                }
            }
            printf("%d\n",ss.size());
        }
        return 0;
    }
    

    再次感觉到容器是个好东西


    展开全文
  • PTA 列车调度

    2018-03-24 17:04:07
    列车调度时间限制300 ms内存限制65536 kB代码长度限制8000 B判题程序Standard作者陈越火车站的列车调度铁轨的结构如下所示。Figure两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行...
  • 火车站的列车调度铁轨的结构如下所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在入口处...
  • 火车站的列车调度铁轨的结构如下所示。 Figure 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟...
  • 列车调度 天梯

    2019-11-21 09:38:10
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...
  • PTA列车调度

    2019-03-29 18:11:41
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...
  • 7 列车调度

    千次阅读 2017-03-11 19:09:07
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...
  • PTA 列车调度 Java

    2020-02-06 15:41:29
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...
  • 列车调度问题PTA

    千次阅读 2018-12-25 21:52:58
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...
  • PTA列车调度C语言版

    2019-12-30 12:35:30
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...
  • PTA 题目 列车调度

    千次阅读 2020-03-27 12:53:31
    火车站的列车调度铁轨的结构如下所示。 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在中有9趟列车,在...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 342
精华内容 136
关键字:

列车调度图