|
题目描述
强迫症小h在整理书库，准备把书全部摆放在书桌上，摆放若干堆。
小h要求：书桌上的每堆书必须按照书本厚度从小到到大排序（也就是每堆书下面的不能比上面的薄，可以一样）。
小h会从书库里一本一本地拿书出来，然后进行摆放，请问小h最少需要摆放多少堆，才能摆好所有书籍。
输入
第一行一个整数，表示书库书本总数量(1≤n≤10^5)
第二行个整数，表示书本厚度（1≤ai≤30000）
输出
输出一个整数，表示小h最少需要摆放堆数。
样例输入
8
389 207 155 300 299 170 158 65
样例输出
2
提示
最少需要摆放两堆
第一堆：398-207-155-65
第二堆：300-299-170-158
分析：这一题就是我的文章，《记录我的拉胯时刻》的文章中提及的，一道稍微进阶的最长递增子序列的模板题。
先分析复杂度！n^5，如果我们直接使用朴素的求解最长递增子序列的方法，复杂度为O(n^2)，很显然是会超时的。
现在转念一想，当初学的利用二分的求解LIS的方法的真正用意了，这个复杂度是O(nlogn)，是不会超时的。
思路是这样的：
按照题目要求的来走，我们的每一堆书都满足最长非严格递减子序列，转念一想，用贪心的思想去思考，我们可以开出一个数组ans用来存储每一个最长非严格递减子序列的最小元素。因此当我们遍历我们输入的内容的时候，当此时的数可以在ans数组里面找到比他更大的或者相等的，那么就替代ans中的这个数。（注意，在ans数组里面找到的比该元素大的数可能不止一个，但是我们要选择最小的一个，这样符合贪心的思想，才能使得一叠书更厚，也就间接使得书的堆数减少了，是不是感觉很想用lower_bound函数？）；而当我们在ans中无法找到比此数更大的数了，怎么办？很明显，无论哪一叠书，我们都没办法放上去，因此自成一派，成为一堆书。这就是运用了贪心的思想。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int ans[10005],len;
int main(){
int n,a;cin>>n;
while(n--){
scanf("%d",&a);
int id=lower_bound(ans,ans+len,a)-ans;
if(id<len)ans[id]=a;
else ans[len++]=a;
}
printf("%d\n",len);
}
|