最长上升子序列 nlogn;也是从别人的博客学来的

#include<iostream>

#include<algorithm>

#define maxn 100000+5

using namespace std;

int n;

int a[maxn];

int solve(int b[],int l)

{

	int f[maxn];//f[i]表示子序列长度为i+1的序列中，末尾元素最小的元素的值

	int k=0;

	f[k++]=b[0];

	for(int i=1;i<l;i++)

	{

		if(b[i]>=f[k-1]) f[k++]=b[i];

		else

		{

			int pos=upper_bound(f,f+k,a[i])-f;

			f[pos]=a[i];

		}

	}

	return k;

}

int main()

{

	cin.sync_with_stdio(false);

	int t;

	cin>>t;

	int flag=1;

	while(t--)

	{

		cin>>n;

		for(int i=0;i<n;i++)

		{

			 int x;

			 cin>>x;

			 a[i]=x-i;

		}

		int re=solve(a,n);

		cout<<"Case "<<"#"<<flag++<<":"<<endl;

		cout<<n-re<<endl;

	}

	return 0;

}