HDU5532 Almost Sorted Array（LIS的nlogn算法）
http://acm.hdu.edu.cn/showproblem.php?pid=5532
题意：给你一个数列，消除一个数以后，是剩下的数列是排序的（递增或递减的）。
题解：直接正反两次LIS即可，如果>=n-1,证明是YES。注意要用到LIS的nlogn算法。
注意元素相等的情况（WA的一晚。。。),数组开小会TLE==。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int a[100005],b[100005],t[100005]; int find(int l,int r,int num) { int mid; while(l<=r) { mid=(l+r)/2; if(num>=t[mid]) l=mid+1; else r=mid-1; } return l; } main() { int N,n,i,len,len1,ans; scanf("%d",&N); while(N--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); len=0; t[0]=-1; for(i=0;i<n;i++) { if(a[i]>=t[len]) t[++len]=a[i]; else { ans=find(1,len,a[i]); t[ans]=a[i]; } } if(len>=n-1) { printf("YES "); continue; } memset(t,0,sizeof(t)); for(i=0;i<n;i++) b[i]=a[n-i-1]; len1=0; t[0]=-1; for(i=0;i<n;i++) { if(b[i]>=t[len1]) t[++len1]=b[i]; else { ans=find(1,len1,b[i]); t[ans]=b[i]; } } if(len1>=n-1) { printf("YES "); continue; } printf("NO "); } }