2806178_ac_309ms_4788k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 80 行

#include <stdio.h>
#include <algorithm>
#define Max 1000001

using namespace std;

int num;
int p;
int a[Max], b[Max], c[Max];

int get(int n)
{
	int max, min, mid;

	min = 0;max = num-1;
	while(min<max)
	{
		mid = (min+max)/2;
		if(n < b[mid])
			max = mid;
		else
			if(n > b[mid])
				min = mid+(min==mid);
			else
				return mid;
	}
	return min;
}

int main()
{
	int i, j, pos;
	int count, ans;
	int max, min, ed;

	scanf("%d",&p);
	ans = p;
	for(i = 0; i < p; i++)
		scanf("%d",&a[i]),b[i] = a[i];
	sort(b,b+p);
	num = 0;
	for(i = 0; i < p; i++)
	{
		j = i;
		b[num++] = b[i];
		while(j<p&&b[j]==b[i])
			j++;
		i = j-1;
	}
	memset(c,-1,sizeof(c));
	count = 0;
	for(i = 0; i < p; i++)
	{
		pos = get(a[i]);
		if(c[pos]==-1)
			count++;
		c[pos] = i;
		if(count==num)
		{
			max = -1;min = p+1;
			for(j = 0; j < num; j++)
			{
				if(c[j]<min)
				{
					ed = j;
					min = c[j];
				}
				if(c[j]>max)
					max = c[j];
			}
			max -= min;
			if(max < ans)
				ans = max;
			count--;
			c[ed] = -1;
		}
	}
	printf("%d\n",ans+1);
	return 0;
}