积木

思路与复杂度

维护 tails[j] 表示已处理前缀中长度为 j+1 的严格递增子序列的最小末尾高度。每个高度用 lower_bound 找到首个不小于它的位置并替换。最终若长度达到 k，tails[k-1] 就是答案，否则为-1。时间 O(n log n)，空间 O(n)，不能用 upper_bound。

正确性与边界

相同长度更小的末尾不会损失任何后续扩展，二分替换维护此最优性质。

参考代码

#include<bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0);int n,k;cin>>n>>k;vector<long long>t;while(n--){long long x;cin>>x;auto it=lower_bound(t.begin(),t.end(),x);if(it==t.end())t.push_back(x);else *it=x;}if((int)t.size()<k)cout<<-1<<"\n";else cout<<t[k-1]<<"\n";}