类似于最长上升子序列,我们存储每一个队伍的队尾f[N],可以证明队伍元素依次递增
假设f[1] > f[2],即第二个队伍中最矮的小朋友比第一个队伍中最矮的小朋友矮,那么我们可以将这个小朋友排在第一个队伍
所以,f[N]也是一个递增序列,那么有以下两种情况
1. 在排队的时候,找到已有队伍中,队尾小朋友身高高于当前小朋友的最小值,即二分中找到大于等于k的第一个数。将当前小朋友插入该队伍末尾,更新该队伍队尾身高值
2. 如果当前小朋友身高比之前所有队伍队尾小朋友身高都高的话,那么新成立一个队
此时你可以发现,和最长上升子序列的代码一样,只是代码代表的意义不同而已
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int cnt;
int f[N];
inline int bs(int k) // 找到大于k的第一个数
{
int l = 0, r = cnt-1;
while (l < r)
{
int mid = l + r >> 1;
if (f[mid] >= k) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
while (scanf("%d", &n) != -1)
{
cnt = 0;
for (int i = 0; i < n; i ++)
{
int t = 0; scanf("%d", &t);
if (cnt == 0) f[cnt ++] = t; // 对于第一个小朋友自成一队
else if (t > f[cnt-1]) // 如果当前小朋友高于此前所有队伍队尾小朋友,那么新成立一队
f[cnt ++] = t;
else // 否则,找到队伍小朋友比当前小朋友高,且身高最相近的队伍进行插入,更新该队伍的队尾身高
{
f[bs(t)] = t;
}
}
cout << cnt << endl;
}
return 0;
}