第一维排序 第二维LIS

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int dp[100010]; int p[100010]; struct node { int x, y, id; }a[100010]; bool cmp(node a, node b) { if(a.x != b.x) return a.x < b.x; return a.y > b.y; } void print(int x) { if(p[x] == -1) { printf("%d", a[x].id); return; } print(p[x]); printf(" %d", a[x].id); } int main() { int n; while(scanf("%d", &n) != EOF) { memset(dp, -1, sizeof(dp)); memset(p, -1, sizeof(p)); for(int i = 1; i <= n; i++) { scanf("%d %d", &a[i].x, &a[i].y); a[i].id = i; } sort(a+1, a+n+1, cmp); dp[1] = 1; int len = 1; for(int i = 2; i <= n; i++) { int l = 1, r = len; while(l <= r) { int m = (l + r) >> 1; if(a[dp[m]].y < a[i].y) l = m+1; else r = m-1; } dp[l] = i; p[i] = dp[l-1]; if(l > len) len = l; } //sort(dp+1, dp+len+1); printf("%d\n", len); print(dp[len]); puts(""); } return 0; }