【问题背景】
zhx 给他的妹子们排序。
【问题描述】
zhx有N个妹子，他对第i个妹子的好感度为ai, 且所有ai两两不相等。现在N个妹子随意站成一 排，他要将她们根据好感度从小到大排序。 他使用的是冒泡排序算法。如果排序过程中 好感度为ai的妹子和好感度为aj的妹子发生了交换， 那么她们之间会发生一场口角。
现在 zhx 想知道， 给定妹子的初始排列， 在排序完成后， 最多存在多少个妹子， 她们任意两 人之间没发生过口角。
正式地， 考虑对数组ai进行冒泡排序， 如果ai和aj在排序过程中发生交换，那么在两个元素之 间连一条边。你需要求出，排序结束后，最多存在多少个元素，其中任意两个元素之间不存在连边。
【输入格式】
第一行两个整数 N， 表示妹子数量。
接下来一行 N 个整数ai，表示初始第 i 个妹子的好感度。
【输出格式】
一行一个整数， 表示最多满足要求的妹子的个数。
【样例输入】
3
3 1 2
【样例输出】
2
【样例解释】
{1, 2}。
【数据规模与约定】
对于30%的数据， 1 ≤n≤ 16。
对于70%的数据， 1 ≤n≤ 5000。
对于100%的数据， 1 ≤n≤ 100000, 0 ≤ai<n。
首先，直接冒泡的复杂度是n^2，然后再瞎搞就是30的暴力啦。其次呢，如果你看出来（其实是瞎猜出来）
if(ai<aj) 不用交换
那么你就get了这个题了，emmmm，其实做题的时候还不知道什么事LIS，但是看数据范围就瞎搞了一个nlogn的做法，瑟瑟发抖。然后并没有A,首先我输出了妹子，其次我的二分写挂啦。
对于70分，我猜是n^2的dp，emmmm，貌似线段树维护优化到nlogn也可以A，qwq待会试一下贴上来。
#include<cstdio> #include<cstring> inline int read() { int f=1; int k=0; char c=getchar(); while(c>‘9‘||c<‘0‘) { if(c==‘-‘) f=-1; c=getchar(); } while(c>=‘0‘&&c<=‘9‘) { k=k*10+c-‘0‘; c=getchar(); } return k*f; } int ma[100010]; int len=0; void ef(int l,int e,int value) { if(l==e) { ma[l]=value;//二分找到后应该是当前位置而不是+1 return; } int m=(l+e)>>1; if(ma[m]>=value) ef(l,m,value); else ef(m+1,e,value); } int main() { freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); int n=read(); int mz; memset(ma,0,sizeof(ma)); for(int i=0;i<n;++i) { mz=read(); if(mz>=ma[len]) { ++len; ma[len]=mz; // printf("%d ",i); } else ef(1,len,mz); } printf("%d\n",len);//输出len，不是mz // for(int i=1;i<=len;++i) printf("%d ",ma[len]); return 0; }
原文：http://www.cnblogs.com/wykjx1314/p/7680192.html