2361865_ac_30ms_3976k.cpp

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

#include <stdio.h>
#include <string.h>

int min(int a,int b)
{
	return a>b?b:a;
}
int a[1000001];
int main()
{
	int mark = 0;
	int n, k, t1, t2;

	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&k);
	if(n==0)
		mark = 1,n++;
	for(int i = 0; i <= n; i++)
		a[i] = n-i;
	t1 = n; t2 = n*2;
	while(1)
	{
		//a[t2] = a[t1]+1;
		for(i = t1+1; i <= t2; i++)
		{
			if(i%2)
				a[i] = a[i-1]+1;
			else
			{
				a[i] = min(a[i/2],a[i-1])+1;
				int j = i;
				while(a[j-1]>a[j]+1)
					a[j-1] = a[j]+1,j--;
			}
		}
		if(t2>k)
			break;
		t1 = t2;t2 *= 2;
	}
	printf("%d\n",a[k]+mark);
	return 1;
}