导弹拦截

int main() { int x; while (cin >> x) a[++n] = x; int len = 1; f[len] = a[1]; for (int i = 2; i <= n; i++) { int l = 0, r = len + 1; while (l + 1 != r) // 找小于a[i]的第一个数 { int mid = (l + r) / 2; if (f[mid] >= a[i])//因为这里维护的是最长不上升子序列 l = mid;//因此这里的l和r应该反着取 else r = mid; //左侧l都是>=a[i],r相反，如果r没变，说明a[len+1]=a[i]; //这时候发现规定的r没变，并且r=len+1（模板的优越性），否则替换末尾值 } f[r] = a[i]; if(r == len + 1) len++; } cout << len << endl; int cnt = 1; g[cnt] = a[1];//g[i]记录的是每次子序列末尾的最小值，但是当我们发现g[mid]>=a[i]， //则可以有更优越的a[i]替换末尾 for (int i = 2; i <= n; i++) { int l = 0, r = cnt + 1; while (l + 1 != r) { int mid = (l + r) / 2; if (g[mid] < a[i])//如果都是<a[i]的值，那么就需要重开系统，这时候发现 l = mid;//居然发现r=cnt+1，那么默认g[r]=a[i] else r = mid; } g[r] = a[i]; if(r == cnt + 1) cnt ++; } cout << cnt << endl; return 0; }