题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1609
题意：
给你一个只由数字"1,2,3"组成的序列a[i]，共n个数。
你可以任意更改这些数字，使得序列中每一种数字都“站在一起”，并且单调不减或不增。
例如："1111222", "332211"...
问你至少更改多少个数字。
题解：
单调不减：求原序列LIS（最长非降子序列），当前答案t1 = n - LIS.
单调不增：求原序列LDS（最长非升子序列），当前答案t2 = n - LDS.
最终答案ans = min(t1,t2).
注：n为30000，求LIS & LDS用nlogn方法。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 30005 using namespace std; int n;
int a[MAX_N];
int d[MAX_N]; int cal_lis()
{
int len=;
d[]=a[];
for(int i=;i<n;i++)
{
if(a[i]>=d[len])
{
d[++len]=a[i];
continue;
}
int lef=;
int rig=len;
while(rig-lef>)
{
int mid=(lef+rig)/;
if(a[i]>=d[mid]) lef=mid;
else rig=mid;
}
int ans;
if(a[i]<d[lef]) ans=;
else ans=lef;
d[ans+]=min(d[ans+],a[i]);
}
return len;
} int cal_lds()
{
int len=;
d[]=a[];
for(int i=;i<n;i++)
{
if(a[i]<=d[len])
{
d[++len]=a[i];
continue;
}
int lef=;
int rig=len;
while(rig-lef>)
{
int mid=(lef+rig)/;
if(a[i]<=d[mid]) lef=mid;
else rig=mid;
}
int ans;
if(a[i]>d[lef]) ans=;
else ans=lef;
d[ans+]=max(d[ans+],a[i]);
}
return len;
} int main()
{
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
}
int v1=cal_lis();
int v2=cal_lds();
cout<<n-max(v1,v2)<<endl;
}