CF 335 div.2-C/div.1-A/605A Sorting Railway Cars_cf335 c

题目链接： http://codeforces.com/problemset/problem/605/A

题目大意：在一条路上有序号为1-n的n辆车以任意顺序放着，现在要对这些车以升序进行排序，每次移动可以将一辆车取出来放到最前面或者最后面，现在问想要完成排序的最少移动次数。

解：一辆一辆地取出来相当于把所有要取的取出来，然后按一定顺序往序列里放，所以，我们先把所有要取的取出来，那么所剩下的，一定是一串连续的上升的序列，如果我们要移动的次数最少，那么所剩的这个序列一定是最长的。所以我们只需要找出相邻数连续的最长上升子序列即可，假设这个子序列长度为k，则最少移动次数为n-k。

我感觉这个题的难度就在于能发现移动的规律性，依次取相当于一次全取出来，不被移动的一定组成一个连续的上升序列。然后，算是贪心吧。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int num[100005], len[100005];
int main()
{
	//freopen("input.txt", "r", stdin);
	int n, ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &num[i]);
	for (int i = 1; i <= n; ++i)
	{
		len[num[i]] = len[num[i] - 1] + 1;
	}
	for (int i = 1; i <= n; ++i)
		if (ans < len[i])
			ans = len[i];
	printf("%d\n", n - ans);
	//system("pause");
	//while (1);
	return 0;
}