算法
本题属于贪心。对于每一个轨道的第x
位置的火车,总是希望第x+1
位置火车(第x
位置的后面)的编号要小于第x
位置火车编号,并且两者编号差值越小越好。比如5 2 4 3 1
,最好的结果是5 4 3 1
和2
,而不是5 2 1
和4 3
,因为两个车编号差值越小,代表这个轨道能容纳的火车可能会更多,可以降低轨道的数目。所以基于此可以考虑对所有轨道最后一辆车的编号进行排序,将待插入的火车从前往后遍历找到第一个大于它的就插入即可。但这样做需要每次都排序,时间复杂度比较高,而我们又希望存储每个轨道末尾火车编号是有序的,所以可以采用二分的方法,每次用二分找到第一个比当前待插入火车编号大的点,然后修改即可;而当当前编号大于序列中最后一个编号时,说明它需要额外开辟一个轨道,直接ways[idx++] = a
即可。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,idx;
int ways[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
if(i==0||a>ways[idx-1]) ways[idx++] = a;
else
{
int l=0,r=idx-1;
while(l<r)
{
int mid = l+r>>1;
if(ways[mid]>a) r=mid;
else l=mid+1;
}
ways[l] = a;
}
}
cout<<idx<<endl;
return 0;
}