8 - 書櫃

domen111

http://hoj.twbbs.org/judge/problem/view/8

乍看之下好像是Insertion sort，但n=300000一定TLE，突然想到泡沫排序法交換次數，難道這題也是BIT!?

其實...上面那段話只是我一開始的想法，和這題的解法一點關係都沒有，就算真的模擬一次Insertion sort不會TLE也還是解不出答案

來認真想一下這題，答案最大一定就是N(把book[N]移到最前面、把book[N-1]移到最前面、把book[N-2]移到最前面...把book[1]移到最前面)，但事實上有些東西並不需要一動，它本來就在正確的位置了，仔細想想，這些不需要移動的書本，最後排序完成後一定是擺在最後面，假設有k本書不用移動，那麼他們的編號一定就是(N,N-1,N-2...N-k+1)，所以就只要O(n)線性從後面掃到前面就...輕鬆AC


短短的code:

[C++] 純文本查看 復制代碼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a[300010];
int main()
{
	ios::sync_with_stdio(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	int now=n;
	for(int i=n-1;i>=0;i--)
	{
		if(a[i]==now)now--;
	}
	cout<<now<<endl;
}