Description



Input



Output



Sample Input

Sample1: 

3 

1 2 3 

Sample2: 

9 

1 3 2 4 8 6 9 5 7



Sample Output

Sample1: 

3 

Sample2: 

5



Data Constraint





思路

这题我用的是贪心做法

首先，一个列车进队，必须满足前面的车的编号大于它。 

不难想到我们的最优方案是让列车入编号刚好大于它的那一队。

所以我们可以用set维护。



代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
int ans,n;
set<int> q;
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d",&x);
        set<int>::iterator j=q.upper_bound(x);
        if(j==q.end()) q.insert(x),ans++;else q.erase(*j),q.insert(x);
    }
    printf("%d",ans);
}

Description





Input





Output





Sample Input



Sample1:

3 

1 2 3



Sample2:

9 

1 3 2 4 8 6 9 5 7

Sample Output



Sample1:

3



Sample2:

5

Data Constraint



Solution

显然，一辆列车开到另一辆列车的后面，一定比新开一条轨道更优。
那么一辆列车要满足什么条件才能停到另一辆的后面呢？
它的序号 X 一定小于前面的列车！不然其他就出不去、无法满足题意了。
于是我们贪心地寻找比 X 大的值且最小的那个位置，停进去即可。
其实我们不需要模拟开出的情况，因为操作是序号更小时才会进行的。
那么当某个序号的列车将要开出时，它的前面一定没有阻挡的列车，因为它们已经开出了。
于是我们只需用一个 Set 维护一下轨道最后一个列车的序号的情况，直接处理即可。
这样的时间复杂度是 O(NlogN) 。
Code

#include<cstdio>
#include<set>
using namespace std;
inline int read()
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
set<int>f;
int main()
{
    int n=read(),ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        f.insert(x);
        set<int>::iterator it=f.find(x);
        if(++it==f.end()) ans++; else f.erase(it);
    }
    printf("%d",ans);
    return 0;
}

T1：



列车调度



题目描述





输入描述





输出描述





样例输入

Sample1: 

3 

1 2 3 

Sample2: 

9 

1 3 2 4 8 6 9 5 7



样例输出

Sample1: 

3 

Sample2: 

5

题解： 

我们发现，如果要使轨道数k最小，那么应尽量在现有的轨道中塞（废话）。 

而要保证倒叙出去，没有列车的编号能大于同一条轨道中前面所有列车的编号（除非它是第一辆） 

那么可以分两种情况讨论： 

1，目前所有轨道的最后一辆列车的编号都小于要塞入的那辆列车的编号 

多加一条轨道，将列车塞进去即可 

2，目前某些轨道的最后一辆列车的编号都小于要塞入的那辆列车的编号 

找到最小的大于当前列车编号的那辆列车所在的轨道，塞入即可。 

解释一下第二种情况， 

设当前要塞入的列车编号为x，轨道1，2的结尾列车编号分别为s1和s2，s2>s1>x。 

如果我们把x放在s1后面，则轨道1接下来只能放编号

这题没什么好说的，就是一个栈的实现，因为当时那个OJ不能用STL，就自己写了一个功能有，但是不完善的栈，反正解出题目了。。。。。。

注意：此题是第二次mooc课程，但是我参加的第一次mooc课，所以ac代码可能不能直接提交，需要修改





列车调度(Train)



描述
某列车调度站的铁道联接结构如图所示。

其中，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。



输入样例1
5 2
1 2 3 5 4




输出样例1
push 
pop 
push 
pop
push
pop
push
push
pop
pop




输入样例2
5 5
3 1 2 4 5




输出样例2
No



限制
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000
时间：2 sec
空间：256MB







AC的代码：
#include <stdio.h>
#define MANX 100005

int Stack[MANX];
int Out[MANX];
int sTop=0;	//栈顶指针

void push(int a)
{
	Stack[++sTop]=a;
}

void pop()
{
	sTop--;
}

int top()
{
	return Stack[sTop];
}

int main()
{
	// in 的时候一定是{1, 2, ..., n}
	int n,m;
	scanf("%d%d",&n,&m);
	
	int i;
	for(i=1;i<=n;i++)
		scanf("%d",&Out[i]);
	
	//算法开始
	int j=0;
	for(i=1;i<=n;i++)
	{
		//如果小于栈顶元素，直接可判断在栈中而无法出栈
		if(Out[i]<top())
		{
			printf("No\n");
			return 0;
		}

		//直到 Out[i] 的元素全部加入栈
		if(j<Out[i])
			while(j!=Out[i])
				push(++j);
		
		if(sTop>m)
		{
			printf("No\n");
			return 0;
		}
		
		if(Out[i]==top())
			pop();
	}

	printf("Yes\n");
	
	return 0;
}