[jzoj 3464] 【NOIP2013模擬聯考6】秀姿勢 {雜湊表 佇列維護}

NO IMAGE

題目

Description
“藍貓淘氣三千問,看藍貓,我有姿勢我自豪!”話說能考上HYSBZ的孩紙們肯定都是很有姿勢的孩紙們,但是大家普遍偏科,都只有一門科目考得好。已知HYSBZ的入學考試科目數量小於等於10^9,而有n個學生參加了入學考試。現在HYSBZ要刷人了,招生辦每一次刷人會把一個科目考得好的人全部刷掉,但是最多不能刷超過K次。(刷就是不錄取)而HYSBZ的校長看錄取名單時,最喜歡看的就是連續都是同一個科目考得好的人。他定義完美學生序列為連續且考得好的科目都為同一門的學生序列。現在招生辦主任想讓你幫他設計一種錄取方案,使得最長的完美學生連續子序列儘量長。
Input
共N 1行,第一行2個正整數n,K,n表示入學考試人數,K表示刷人次數上限。
接下來N行,每行僅一個正整數Ai,為i號學生所考得好的科目。
Output
僅1個正整數,為最長的最長完美學生連續子序列。


解題思路

10%演算法:還是一個很神奇的演算法,不明覺厲。
100%演算法:用佇列維護一個區間,使得這個區間的擅長科目數量不超過 K 1″ role=”presentation”>K 1K 1K 1,
那麼統計出來的每個合法區間的眾數的數量的最大值便為答案。具體操作
如下:
(1).首先新增第一個元素入佇列,此時Head=Tail=1″ role=”presentation”>Head=Tail=1Head=Tail=1 Head=Tail=1
(2).接下來不斷新增元素入隊,當佇列內元素種類不大於 K 1″ role=”presentation”>K 1K 1K 1 時統計答案。
(3).當佇列裡的元素種類大於 K 1″ role=”presentation”>K 1K 1K 1 時,不斷將佇列頭部的元素出隊,直到
佇列內元素種類小於等於K 1″ role=”presentation”>K 1K 1 K 1,這時要記得也要統計答案。
這便是這道題的演算法。時間複雜度 O(n)” role=”presentation”>O(n)O(n)O(n)
資料有一定梯度,其餘維護區間方法也能得分。


程式碼

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int inn=1000007; 
queue<int> q;
int h[inn],num[inn],a[100005],n,p,k,ans;
int hash(int x)
{
int tmp=x%inn;
while (h[tmp]!=0&&h[tmp]!=x) tmp=(tmp 1)%inn;
return tmp;
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i  )
scanf("%d",&a[i]);
for (int i=1;i<=n;i  )
{
int ha=hash(a[i]);
q.push(a[i]);
if (h[ha]==0)
{
p  ;
h[ha]=a[i];
while (p>k 1)
{
int x=q.front();  q.pop();
if (--num[hash(x)]==0) {h[hash(x)]=0; p--;}
}
}
num[ha]  ;
ans=max(ans,num[ha]);
}
printf("%d",ans);
}