T2848 列车调度（二分或dp）

题目背景

自行脑补，

题目描述

有N辆列车，标记为1,2,3,…,N。它们按照一定的次序进站，站台共有K个轨道，轨道遵从先进先出的原则。列车进入站台内的轨道后可以等待任意时间后出站，且所有列车不可后退。现在要使出站的顺序变为N,N-1,N-2,…,1，询问K的最小值是多少。（也就是最少需要几个轨道）

输入输出格式

输入格式：

输入共2行。

 第 1 行包含1个正整数N，表示N辆列车。

 第 2 行包含N个正整数，为1至N的一个排列，表示进站次序。

输出格式：

 输出共1行，包含1个整数，表示站台内轨道数K的最小值。

输入输出样例

输入样例#1：

3

1 2 3

输出样例#1：

输入样例#2：

9

1 3 2 4 8 6 9 5 7

输出样例#2：

说明

 对于30%的数据，N≤10；

 对于70%的数据，N≤2000；

 对于100%的数据，N≤100000

分析：

属于一类模型转换的题。此题在poj之旅中应有原题。在此重述，加深印象。

我们可以假设结果是K，假设这个序列的最长上升序列为L，我们可以证明出K>=L,所以K的最小值只能是L。

具体证明：

由于问题是一个队列，只能先进先出，所以K的最小值实际就是将原序列划分成几个下降序列，如果K<=L,那么就无法将L个递增的数字无矛盾的放入K个下降序列，即必然在某一个下降序列中存在a>b的。这其实就是鸽笼原理。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

int a[maxn];

int n;

int main(){

    scanf("%d",&n);

    memset(a,0x3f,sizeof(a));

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

        int x;

        scanf("%d",&x);

        *lower_bound(a+,a+n+,x)=x;

    }

    printf("%d",lower_bound(a+,a+n+,a[])-a-);

    return ;

}

巴特西

T2848 列车调度（二分或dp）

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章