学步园

本题目，我用了一种较简单的解题方法依然求LIS

但不同的是要先进行排序，排序方法为先按x 升序排序，在按照y降序排序，然后用nlogn算法即可求解LIS

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1000010000
const int maxn = 100100;
struct node {
int x,y,id;
node (int x=0,int y=0,int id=0):x(x),y(y),id(id){}
bool operator <(const node& rhs) const{
return x<rhs.x||x==rhs.x&&y>rhs.y;
}
}a[maxn];
int n,d[maxn],g[maxn];
int main()
{
    while(scanf("%d",&n)==1){
          for(int i=0;i<n;i++){
              scanf("%d %d",&a[i].x,&a[i].y);
              a[i].id=i+1;
          }
          for(int i=1;i<=n;i++) g[i]=INF;
          sort(a,a+n);
          int ans=1;
          for(int i=0;i<n;i++){
              int posi=lower_bound(g+1,g+n+1,a[i].y)-g;
              g[posi]=a[i].y;
              d[i]=posi;
              ans=max(ans,posi);
          }
          int temp=ans,nx,ny;
          printf("%d\n",ans);
          for(int i=n-1;i>=0;i--){
                if(d[i]==temp){
                      if(temp==ans||nx>a[i].x&&ny>a[i].y){
                          nx=a[i].x; ny=a[i].y;
                          if(temp!=ans) printf(" ");
                          temp--;
                          printf("%d",a[i].id);
                      }
                }
          }
          printf("\n");
    }
    return 0;
}