Ignatius and the Princess II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4803    Accepted Submission(s): 2885

6 4

11 8

1 2 3 5 6 4

1 2 3 4 5 6 7 9 8 11 10

非常经典的一条取数列问题，就是找到一个数列中第m大的数列。

假设使用暴力法就须要O(n!)时间效率。使用特别的方法直接取出数列。那么时间效率就是O(n)了。

方法就是使用m生成一个取数数列，依据取数数列直接取出d第m大的数，就能够了。

要规范一下函数的接口。形成良好的编程习惯。

网易叫我改投他们的运营，通知明天笔试。我突然间好像说，f you！

你运营的能写出我这么美丽的代码吗？你运营的须要这么好的算法嘛？你运营的须要数十万行的代码经验吗？

#include <stdio.h>

#include <vector>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <string>

#include <limits.h>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;

const int MAX_N = 1001;

int arr[MAX_N], N, M, tbl[MAX_N], a2[MAX_N];

bool genTbl(int tbl[], int n, int m)//n 位。 第m个

{

	--m;

	if (m < 0) return false;

	tbl[n-1] = 0;

	for (int d = 2, i = n-2; i >= 0 ; d++, i--)

	{

		tbl[i] = m%d;

		m /= d;

	}

	return true;

}

void eraseElement(int arr[], int i, int *n)

{

	(*n)--;

	for (; i < *n; i++)

	{

		arr[i] = arr[i+1];

	}

}

void getSequence(int res[], int arr[], int tbl[], int n)

{

	int i = 0;

	int *p = arr;

	while (n)

	{

		for ( ; n > 0 && tbl[i] == 0; n--, p++, i++)

		{

			res[i] = *p;

		}

		if (!n) return ;

		res[i] = p[tbl[i]];

		eraseElement(p, tbl[i], &n);

		i++;

	}

}

int main()

{

	while (~scanf("%d %d", &N, &M))

	{

		for (int i = 0; i < N; i++)

		{

			arr[i] = i+1;

		}

		genTbl(tbl, N, M);

		getSequence(a2, arr, tbl, N);

		printf("%d", a2[0]);

		for (int i = 1; i < N; i++)

		{

			printf(" %d", a2[i]);

		}

		putchar('\n');

	}

	return 0;

}