SGU--199 beautiful people

墨蓝 2022-08-11 03:26 122阅读 0赞

题意：

一个土豪俱乐部里面的人勾心斗角，如果他们两个各有长处，则彼此不服气，如果一方完全弱于另一方则对其服服帖帖；给出你每个人的特征值，这里仅两个。S代表Strength，B代表beauty。俱乐部部长为了办一场和睦的晚会，也想邀请最多的成员，让你计算一下最多邀请多少人，并输出他们的序号。期中受邀请的两人必满足

s1<s2&&b1<b2。

解题：

看到这一题首先想到的应该就是最长上升子序列，可是这一题有两个关键字，应该怎么办呢？

当然把会员都按升序排列也行，这需要在判断的过程中判断两个条件，不过也可以吧第二个关键字按降序排列，因为第一个关键字不能相等。（其实在没参考别人的代码之前我用的是前者+\_+)

本题要说考察的算法话就是O（n\*logn)的最长上升子序列了，就是维护一个上升数组就行了；

而要注意的就是输出，按一个关键排列的输出根本不行（我二到按一个关键字的方式直接交了好几次，当然肯定wa）把排序后的编号存到数组中，并且存储前面的节点。

其实题目没要求，你按顺序输出，但是你也可以自定义个cmp，按编号为关键字sort一下，超不超时不敢保证，因为还要进行一系列操作，测试数据我不知道.....

#include <cstdio>
      #include <cstring>
      #include <cstdlib>
      #include <iostream>
      #include <algorithm>
      using namespace std;
      const int N = 100010;
      struct peo
      {
          int s,b,id;
          void read()
          {
          	scanf("%d%d",&s,&b);
          }
          bool operator < (const peo &t)const 
          {
          	if(s==t.s)return b>t.b;
          	else return s<t.s;
          }
      }mem[N];
      
     int id[N],prev[N];
     int main()
     {
       int i,len,n;
       scanf("%d",&n);
       for (i = 1;i <= n;i++)
        {
           mem[i].read();
           mem[i].id = i;
       }
       sort(mem + 1,mem + 1 + n);//n*log（n）最糟糕的将近a*1000W
       len = 1, id[1] = 1;
       for (i = 2;i <= n;i++)
        {
           if (mem[i].b > mem[id[len]].b) 
    	   {
               len++;
               id[len] = i;
               prev[i] = id[len - 1];
               continue;
           }
           int low = 1,high = len;//节时，二分查找
           while (low < high)
    	    {
               int mid = (low + high) >> 1;
               if (mem[id[mid]].b < mem[i].b)
    		   {
                   low= mid + 1;
               }else 
    		   {
                   high = mid;
               }
           }
           id[low] = i;
           prev[i] = id[low - 1];
       }
     
       printf("%d\n",len);
       for (i = id[len];i;i = prev[i])
        {
           printf("%d ",mem[i].id);
        }
       putchar(10);//printf("\n");
       return 0;
     }