3063142_ac_0ms_168k.cpp

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

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, a[10000];

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 = 1, i, x, max;

	while(scanf("%d",&a[0])==1&&a[0]!=-1)
	{
		printf("Test #%d:\n",cas++);
		n = 1;
		while(scanf("%d",&a[n])==1&&a[n]!=-1)
			n++;
		reverse(a,a+n);
		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("  maximum possible interceptions: %d\n\n",max+1);
	}
	return 0;
}