SGU--199 beautiful people-蒲公英云

SGU--199 beautiful people

墨蓝 2022-08-11 03:26 183阅读 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;
 }