這個(gè)題目是Sherlock推薦我做的。
題目意思是給一個(gè)長(zhǎng)度為n（n <= 100000）的序列，里面的數(shù)滿足1 <= a[i] <= n。要找一個(gè)最長(zhǎng)的連續(xù)子串，使得這個(gè)子串是1..k的一個(gè)排列。
昨天晚上mmd想了個(gè)n^(3/2)的算法，今天Sherlock想了個(gè)nlogn的算法。我一直在考慮有沒有O(n)的算法。我覺得應(yīng)該有的。
今天晚上吃飯的時(shí)候忽然想出來了。回來寫了果然AC。
下面是我的算法：
注意到滿足題目要求的序列必有如下性質(zhì)：
1。最大值等于長(zhǎng)度
2。必含1
3。序列和為k * (k + 1) / 2
4。序列內(nèi)元素不重復(fù)
如果一個(gè)序列同時(shí)滿足性質(zhì)3，4，那么一定符合題目要求。
于是如果做了O(n)的預(yù)處理，可以用O(1)的時(shí)間驗(yàn)證某序列是否滿足題目要求。
然后我的算法就順理成章了：
1。預(yù)處理s[i]，為序列的部分和
2。預(yù)處理rl[i]，為從i開始往右，最長(zhǎng)的不重復(fù)序列的末端的下標(biāo)
3。預(yù)處理m[i]，為從i開始，到i右邊的第一個(gè)1（或者最右端），這一段數(shù)的最大值。
4。枚舉左端點(diǎn)lp，則lp到其右邊的第一個(gè)1（或者最右端）中的最大值為m[lp]。把m[lp]作為序列長(zhǎng)度，則序列的右端點(diǎn)為lp + m[lp] - 1。利用s[i]和rl[i]數(shù)組可以驗(yàn)證這段序列是否滿足題目要求，若滿足，就更新最優(yōu)解。
5。把輸入序列反過來，重復(fù)步驟1－4。
以上每步的時(shí)間復(fù)雜度都是O(n)，故算法總的時(shí)間復(fù)雜度也是O(n)。
下面是我的代碼
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2008-1-4 18:06:14
File Name: spoj744.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 100010;
int n;
int a[maxn];
int s[maxn];
int rl[maxn];
int hash[maxn];
int m[maxn];
int calc()
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = a[i] + s[i - 1];
memset(hash, 0, sizeof(hash));
for (int i = 1, j = 1; i <= n; i++)
{
while (j <= n && hash[a[j]] == 0)
hash[a[j++]] = 1;
rl[i] = j - 1;
hash[a[i]] = 0;
}
for (int i = n; i >= 1; i--)
if (a[i] == 1)
m[i] = 1;
else if (i == n)
m[i] = a[i];
else
m[i] = max(m[i + 1], a[i]);
int ret = 0;
for (int i = 1; i <= n; i++)
if (rl[i] >= i + m[i] - 1 && s[i + m[i] - 1] - s[i - 1] == m[i] * (m[i] + 1) / 2)
ret >?= m[i];
return ret;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = calc();
reverse(a + 1, a + n + 1);
ans >?= calc();
printf("%d\n", ans);
return 0;
}