本文共 1189 字，大约阅读时间需要 3 分钟。
依据问题转换成最长不降子序列问题。
10^9的输入数据计算起来还是挺花时间的。由于这里仅仅能使用O(nlgn)时间复杂度了。
只是证明是能够算出10^9个数据的。
由于时间限制是5s.
#include #include #include #include #include #include #include #include #include #include #include using namespace std;const int MAX_N = 20;vector arr, a2;int N;inline int lSon(int rt) { return rt<<1|1; }inline int rSon(int rt) { return (rt<<1)+2; }void postOrder(int rt, int &v){ int l = lSon(rt), r = rSon(rt); if (l < N) postOrder(l, v); if (r < N) postOrder(r, ++v); a2.push_back(arr[rt]-v);}int biGetIndex(int low, int up, int v){ while (low <= up) { int mid = low + ((up-low)>>1); if (v < a2[mid]) up = mid-1; else low = mid+1; } return low;}int LIS(){ int j = 0; for (int i = 1; i < N; i++) { if (a2[i] >= a2[j]) a2[++j] = a2[i]; else { int id = biGetIndex(0, j, a2[i]); a2[id] = a2[i]; } } return j+1;}int main(){ int a; scanf("%d", &N); arr.clear(), a2.clear(); while (scanf("%d", &a) != EOF) { arr.push_back(a); } N = (int) arr.size(); int v = 0; postOrder(0, v); int len = LIS(); printf("%d\n", N-len); return 0;}
转载于:https://www.cnblogs.com/lytwajue/p/6758611.html