SGU 199 Beautiful People(最长上升子序列)

题意:有一个俱乐部,俱乐部里面有n个人,每个人有一个强壮值和美丽值,如果某个人在某方面不能完胜或完败某个人的话,那么这两个人就不会产生矛盾!!现在俱乐部要举行一次聚会。。怎样召集人使得最多的人数两两不矛盾。。

解题思路:比较巧妙的一个最长上升子序列的算法,其中,解法是按照从强壮值从升序,美丽值在强壮值相等的时候降序,这样直接进行最长上升子序列再记录路径就能够得到答案(这里面不会产生使得序列长度变短或变长,,读者想一下)

解题代码:

  1 // File Name: g.c
  2 // Author: darkdream
  3 // Created Time: 2013年09月03日 星期二 16时02分52秒
  4 
  5 #include<stdio.h>
  6 #include<string.h>
  7 #include<stdlib.h>
  8 #include<time.h>
  9 #include<math.h>
 10 #include<ctype.h>
 11 #define maxn  100005 
 12 struct node2{
 13   int x, y,num;
 14 }first[maxn],stack[maxn];
 15 int pre[maxn];
 16 int cmp1(const void * a,const void *b)
 17 {
 18    if((*(node2*)a).x == (*(node2*)b).x)
 19    {
 20       return (*(node2*)b).y - (*(node2*)a).y;
 21    }
 22    else return (*(node2*)a).x - (*(node2*)b).x;
 23 }
 24 void print(int x)
 25 {
 26   while(1)
 27   {
 28     printf("%d ",x);
 29     if(pre[x] == 0 )
 30     {    
 31         return ;
 32     }
 33     x = pre[x];
 34     printf("%d ",x);
 35   }
 36     
 37 }
 38 int find(int flor,int y)
 39 {
 40    int l = 1; 
 41    int r = flor;
 42    while(l <= r)
 43    {
 44       int mid = (l+r)/2;
 45       if(stack[mid].y < y )
 46           if(stack[mid].y >= y)
 47               return mid + 1; 
 48           else 
 49               l = mid  +1;
 50       else 
 51           r = mid - 1;
 52    }
 53    return l;
 54 }
 55 void slove(int n)
 56 {
 57    memset(pre,0,sizeof(pre));
 58    stack[0].y = 0 ;
 59    stack[0].x = 0 ;
 60    stack[0].num = 0;
 61    int flor = 0 ;
 62    for(int  i = 1;i <= n ;i ++)
 63    {
 64       if(first[i].y > stack[flor].y)
 65       {
 66          flor++;
 67          stack[flor].y = first[i].y;
 68          stack[flor].num = first[i].num;
 69          stack[flor].x = first[i].x;
 70          pre[first[i].num] = stack[flor-1].num;   
 71       }
 72       else {
 73         int low = find(flor,first[i].y);
 74         stack[low].y = first[i].y ; 
 75         stack[low].num = first[i].num;
 76         stack[low].x = first[i].x;
 77         pre[first[i].num] = stack[low-1].num;
 78       }
 79 
 80    }
 81    printf("%d
",flor);
 82    print(stack[flor].num);
 83    printf("
");   
 84    
 85 }
 86 
 87 int main(){
 88 
 89    //freopen("/home/plac/problem/input.txt","r",stdin);
 90    //freopen("/home/plac/problem/output.txt","w",stdout);
 91    int n;
 92    while(scanf("%d
",&n) != EOF)
 93    {
 94        for(int i = 1;i <= n;i ++)
 95       { 
 96         scanf("%d %d",&first[i].x,&first[i].y);
 97         first[i].num = i ; 
 98       }
 99       qsort(first+1,n,sizeof(node2),cmp1);
100       slove(n);
101    }
102 return 0 ;
103 }
View Code
没有梦想,何谈远方
原文地址:https://www.cnblogs.com/zyue/p/3300727.html