【最长递增子序列O(nlgn)算法】HDU 1025

基德KID.1412

http://acm.hdu.edu.cn/showproblem.php?pid=1025

很难说清楚，自己模拟几下就会慢慢明白，模板题
求的是最长递增子序列的长度

#include <iostream>#include <algorithm>#include <string>//#include <map>#include <queue>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define LL __int64#define inf 0x3fffffff#define M 500005int v[M];int main(){int n, i, tv, x, cc = 1, top;while (~scanf ("%d", &n)){memset (v, 0, sizeof(v));for (i = 0; i < n; i++){scanf ("%d%d", &x, &tv);v[x-1] = tv;}/********************模板********************/top = 0;for (i = 0; i < n; i++){int *p = lower_bound (v, v+top, v);if (p - v == top)++top;*p = v;}/********************模板********************/printf ("Case %d:\n", cc++);if (top <= 1)printf ("My king, at most %d road can be built.\n\n", top);elseprintf ("My king, at most %d roads can be built.\n\n", top);}    return 0;}