本文共 958 字，大约阅读时间需要 3 分钟。
最长上升子序列的nlogn的解法，不过要注意的是 x按从小到大排序，y要按从大到小排序。对于同样的x，在维护的单调数组中y应该保留较小的那个。
#include #include #include #include #include #include #include #include using namespace std;const int maxn = 111111;typedef long long LL;struct Node{ int x; int y; int id;}node1[maxn],node[maxn];int erfen(int a[], int l, int r, int key){ int ans = -1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] > key) { ans = mid; } if (a[mid] > key) r = mid - 1; else l = mid + 1; } return ans;}int cmp(const Node &a,const Node &b){ if(a.x==b.x) return a.y>b.y; return a.x > T; while (T--){ cin >> n; for (int i = 1; i <= n; i++){ scanf("%d%d", &node[i].x, &node[i].y); node[i].id = i; node1[i] = node[i]; } sort(node + 1, node + 1 + n, cmp); cnt = 1; ans[cnt] = node[1].y; vis[cnt++] = node[1].id; father[node[1].id] = node[1].id; //cout<
转载于:https://www.cnblogs.com/yigexigua/p/4125079.html