趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 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[i];
int now=n;
for(int i=n-1;i>=0;i--)
{
if(a[i]==now)now--;
}
cout<<now<<endl;
}
|