c++学习笔记第一篇 列车调度问题 |
您所在的位置:网站首页 › 产品a的结构文件如图所示,其中c › c++学习笔记第一篇 列车调度问题 |
c++学习笔记第一篇 列车调度问题 题目 列车调度 描述 某列车调度站的铁道联接结构如Figure 1所示。 其中,A为入口,B为出口,S为中转盲端。所有铁道均为单轨单向式:列车行驶的方向只能是从A到S,再从S到B;另外,不允许超车。因为车厢可在S中驻留,所以它们从B端驶出的次序,可能与从A端驶入的次序不同。不过S的容量有限,同时驻留的车厢不得超过m节。 设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道,按照以上交通规则,这些车厢能否以{a1, a2, …, an}的次序,重新排列后从B端驶出。如果可行,应该以怎样 的次序操作? 输入 共两行。 第一行为两个整数n,m。 第二行为以空格分隔的n个整数,保证为{1, 2, …, n}的一个排列,表示待判断可行性的驶出序列{a1,a2,…,an}。 输出 若驶出序列可行,则输出操作序列,其中push表示车厢从A进入S,pop表示车厢从S进入B,每个操作占一行。 若不可行,则输出No。 样例 Example 1 Input 5 2 1 2 3 5 4 Output push pop push pop push pop push push pop pop Example 2 Input 5 5 3 1 2 4 5 Output no 限制 1 ≤ n ≤ 1,600,000 0 ≤ m ≤ 1,600,000 时间:2 sec 空间:256 MB 代码实现 #include "stdafx.h" #include #include using namespace std; int main() { int a[50], c[50]; bool operation[50]; int i = 0; int t, t1, m, m1 = 0, n, i1 = 0; cin >> t; for (t1 = 0; t1 < t; t1++) { cin >> n >> m; for (i = 0; i < n; i++) { cin >> a[i]; } int step = 0, b = 1; stacks; s.push(0); for (i = 0; i < n; i++) { while (s.top() < a[i]) { s.push(b++); operation[step++] = true; } if (s.size()>m + 1) { cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |