首页 > > 程序设计 > C/C++ >

Beautiful People SGU - 199 ZOJ - 2319

2018-06-17 21:44:34来源：未知阅读 ()

最长上升子序列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

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct P
 5 {
 6     int a1,a2,num;
 7     bool operator<(const P& b)    const
 8     {
 9         return a1<b.a1||(a1==b.a1&&a2>b.a2);
10     }
11 };
12 bool cmp(const P& a,const P& b)
13 {
14     return a.a2<b.a2;
15 }
16 P a[100100],s[100100];
17 int f[100100],len,n,t;
18 int main()
19 {
20     int i,j;
21     scanf("%d",&n);
22     for(i=1;i<=n;i++)
23         scanf("%d%d",&a[i].a1,&a[i].a2),a[i].num=i;
24     sort(a+1,a+n+1);
25     for(i=1;i<=n;i++)
26     {
27         t=lower_bound(s+1,s+len+1,a[i],cmp)-s;
28         s[t]=a[i];
29         f[i]=t;
30         len=max(len,t);
31     }
32     printf("%d\n",len);
33     for(i=n,j=len;i>=1;i--)
34         if(f[i]==j)
35         {
36             printf("%d ",a[i].num);
37             j--;
38         }
39     return 0;
40 }