竹園論壇

標題: 8 - 書櫃 [打印本頁]

作者: domen111 時間: 2014-11-13 08:59
標題: 8 - 書櫃
本帖最後由 domen111 於 2014-11-13 09:08 編輯

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;

        int now=n;

        for(int i=n-1;i>=0;i--)

        {

                if(a==now)now--;

        }

        cout<<now<<endl;

}