3038674_ac_187ms_2224k.c

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

#include <stdio.h>
#include <string.h>
#define max 200005

int n, m, now;
int id[max], len, array[max], track[max], pos[max], order[max], num[max];

int find(int t)
{
	int l, r, mid;
	
	if(len==0||array[len-1]>t)
		return -1;
	l = 0;r = len-1;
	while(l < r)
	{
		mid = (l+r)/2;
		if(array[mid] > t)
		{
			l = mid+(l==mid);
		}
		else
		{
			if(array[mid] < t)
			{
				r = mid;
			}
			else
			{
				return mid;
			}
		}
	}
	return l;
}

int main()
{
	int i, j, p;

	while(scanf("%d%d",&n,&m)==2)
	{
		if(m==0&&n==0)
		{
			break;
		}
		memset(num,0,sizeof(num));
		for(i = 0; i < n; i++)
		{
			scanf("%d",&id[i]);
		}
		len = 0;now = 0;
		for(i = 0; i < n&&len <= m; i++)
		{
			p = find(id[i]);
			if(p==-1)
			{
				pos[i] = len+1;
				num[len]++;
				array[len++] = id[i];
			}
			else
			{
				pos[i] = p+1;
				num[p]++;
				array[p] = id[i];
			}
		}
		if(len > m)
		{
			puts("Transportation failed");
		}
		else
		{
			for(i = 0; i < n-1; i++)
			{
				printf("%d ",pos[i]);
			}
			printf("%d\n",pos[i]);
			for(i = len-1; i >= 0; i--)
			{
				for(j = 0; j < num[i]; j++)
				{
					printf("%d ",i+1);
				}
			}
			printf("\n");
		}
	}
	return 1;
}