2010年02月17日星期三.sgu199nlogn
最长上升子序列
sgu199: 最长上升子序列
题意：两个关键字，求对两个关键字都成立的最长上升子序列。
也就是这个序列的后一个元素的两个关键字都大于前一个的对应元素。
按照第一关键字升序排列，第二关键字降序排列。
然后对这个序列的第二关键字求最长上升子序列，即是答案。
要注意这个序列不能有等于,并且要记录这个生成的序列。
我的这个写法是一般的二分搜索，比较容易。
还有一个比较难理解的二分，看这里
http://acmicpc.org.cn/wiki/index.php?title=SGU_199_Solution
1
2 const int N = 100010;
3 struct L {
4 int v1,v2,idx;
5 }a[N];
6
7 bool cmp(const L &a,const L & b)
8 {
9 if (a.v1 != b.v1) {
10 return a.v1 < b.v1;
11 }
12 return a.v2 > b.v2;
13 }
14 int idx[N],len,n,prev[N];
15 int main()
16 {
17 int i;
18 scanf("%d",&n);
19 for (i = 1;i <= n;i++) {
20 scanf("%d %d",&a[i].v1,&a[i].v2);
21 a[i].idx = i;
22 }
23 sort(a + 1,a + 1 + n,cmp);
24 len = 1, idx[1] = 1;
25 for (i = 2;i <= n;i++) {
26 if (a[i].v2 > a[idx[len]].v2) {
27 len++;
28 idx[len] = i;
29 prev[i] = idx[len - 1];
30 continue;
31 }
32 int L = 1,R = len;
33 while (L < R) {
34 int mid = (L + R) >> 1;
35 if (a[idx[mid]].v2 < a[i].v2) {
36 L = mid + 1;
37 }else {
38 R = mid;
39 }
40 }
41 idx[L] = i;
42 prev[i] = idx[L - 1];
43 }
44
45 printf("%d\n",len);
46 for (i = idx[len];i;i = prev[i]) {
47 printf("%d ",a[i].idx);
48 }
49 putchar(10);
50 return 0;
51 }