Beautiful People SGU - 199 ZOJ

最长上升子序列O(n log n)：http://www.cnblogs.com/hehe54321/p/cf-340d.html

题目：https://cn.vjudge.net/problem/ZOJ-2319

https://cn.vjudge.net/problem/SGU-199

题意：给出一种数据，它有两个属性s和b。现在有它的两个实例x和y。定义如果 x.s<y.s&&x.b<y.b 或者 x.s>y.s&&x.b>y.b 那么x与y不相冲突，否则x与y冲突。在给出的n个数据中选出最多的数据，使得其中任意两个数据不相冲突。

思路：

直觉给出的思路是按照s、b分别为第一、二关键字将原数据排序，然后O(n log n)求最长上升子序列。但是实际写了之后会发现这么做有问题，因为如果第一个数据的s大于第二个数据的s，第一个的b小于第二个的b，那么取第一个数据还是第二个数据不好是不一定的。或者说，这种数据如果a不大于b那么a也不一定小于等于b。（反正就是不行...）

正确做法就是稍微变一下，先按照s为关键字排序，然后按照b为关键字求最长上升子序列。当然，这里的最长上升子序列要求s也是严格小于，而不只是b严格小于，因此多了一些细节需要处理。这里用的方法类似这个，就是一些小技巧 http://blog.csdn.net/scnu_jiechao/article/details/40670393

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 struct P

 {

     int a1,a2,num;

     bool operator<(const P& b)    const

     {

         return a1<b.a1||(a1==b.a1&&a2>b.a2);

     }

 };

 bool cmp(const P& a,const P& b)

 {

     return a.a2<b.a2;

 }

 P a[],s[];

 int f[],len,n,t;

 int main()

 {

     int i,j;

     scanf("%d",&n);

     for(i=;i<=n;i++)

         scanf("%d%d",&a[i].a1,&a[i].a2),a[i].num=i;

     sort(a+,a+n+);

     for(i=;i<=n;i++)

     {

         t=lower_bound(s+,s+len+,a[i],cmp)-s;

         s[t]=a[i];

         f[i]=t;

         len=max(len,t);

     }

     printf("%d\n",len);

     for(i=n,j=len;i>=;i--)

         if(f[i]==j)

         {

             printf("%d ",a[i].num);

             j--;

         }

     return ;

 }

巴特西

Beautiful People SGU - 199 ZOJ - 2319

最新文章

热门文章