3063157_ac_62ms_300k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int n, a[40010];

int s(int m,int p,int q)
{
	int t;
	while(p<=q)
	{
		t=(p+q)/2;
		if(a[t]<=m) p=t+1;
		else
		{
			if(t-1<0||a[t-1]<=m) return t;
			else q=t-1;
		}
	}
	return -1;
}

int main()
{
	int cas, i, x, max;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d",&n);
		for (i = 0; i < n; i++)
		{
			scanf("%d",&a[i]);
		}
		max = 0;
		for(i = 1; i < n; i++)
		{
			if(a[i] < a[0]) 
				a[0] = a[i];
			else 
			{
				if(a[i] >= a[max]) 
				{
					max++; 
					a[max]=a[i];
				}
				else 
				{
					x = s(a[i],0,max);
					a[x]=a[i];
				}
			}
		}
		printf("%d\n",max+1);
	}
	return 0;
}