HDU 1051 Wooden Sticks【LIS】

题意:给出n个木头的重量wi,长度li,如果满足w[i+1]>=w[i]且l[i+1]>=l[i],则不用耗费另外的加工时间,问至少需要多长时间加工完这些木头。

第一次做这一题目也没有做出来---而且也是好久以前---于是又看题解了---

发现和将木材按两个关键字(先按重量由大到小排,如果重量相等的话则按长度由大到小排)排序后,和导弹拦截系统是一样的了,求长度的最长上升子序列。

自己写的二分查找一直输不出结果----555555

后来用了题解里面的lower_bound函数

搜了一点lower_bound的用法

和二分查找类似,lower_bound是将一个数a插入到给定的序列[first,end)中第一个不小于a的位置, 如果该序列中所有的数都小于a,那么返回end,a插入到end位置上

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
struct node
{
int l,r;
} a[maxn];
int cmp(node n1,node n2)
{
if(n1.l!=n2.l) return n1.l>n2.l;
return n1.r>n2.r;
} int main()
{
int ncase,n,i,j,len,tmp,f[maxn];
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d %d",&a[i].l,&a[i].r);
sort(a+,a+n+,cmp);
len=;
f[len]=a[].r;
for(i=;i<=n;i++)
{
if(a[i].r>f[len])
{
len++;
f[len]=a[i].r;
}
else
{
tmp=lower_bound(f+,f++len,a[i].r)-f;
f[tmp]=a[i].r;
}
}
printf("%d\n",len);
}
}
上一篇:SQL优化 MySQL版 - 避免索引失效原则(二)


下一篇:iOS - YYAdd对UIDevice的拓展