第一次做CF的contest...昨天的Easy題目刷了5道回去睡了..今天的比賽開始還是很順利的..唰唰兩道大水題很快AC..但就沒有然後了...A題我看了下沒看懂..就專攻E題..比賽結束後才做出來...
本題看數據范圍..就只能是O(n)或者O(nlogn)的算法..所以不可能是DP..而O(nlogn)也找不到要二分的理由..所以這題的思路應直奔O(n)的算法...既然是O(n)..那麼感性的估計就是從1掃到n..遍歷的同時進行處理..掃完了結果就出來了..一邊掃可以一邊對1到當前位置 t 的 sum[1~m] 進行計數...並且可以根據當前長度 t 以及當前位顏色x: t-sum[x] 得出要刪掉多少個Cube才能使這1~t中sum[x]個x連續..那麼問題的關鍵就出來了..若 t-sum[x]>k 了..顯然就要要不得了..該如何處理?..
我記錄這麼幾個信息..s[x]代表當前掃到 t 位置時 x 顏色的個數..b[x]代表上一次可行的x起點位置..last[x]代表最近一個x段起點的位置..point[i]紀錄了每一點的信息..包括next..也就是說失敗了跳到後面哪個位置...w代表小於等於 i 時有多少個與 i 位顏色相同的Cube...
然後..就看我程序吧...
Program:
[cpp]
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#define oo 2000000000
#define ll long long
using namespace std;
struct node
{
int next,w;
}point[200005];
int s[200005],b[200005],last[200005],n,m,k,x,q;
int main()
{
int t,ans,m,p;
memset(s,0,sizeof(s));
memset(point,0,sizeof(point));
memset(b,0,sizeof(b));
scanf("%d%d%d",&n,&m,&k);
ans=q=0;
for (t=1;t<=n;t++)
{
scanf("%d",&x);
s[x]++;
if (!b[x])
{
b[x]=t;
last[x]=t;
point[t].w=s[x];
}else
if (x!=q)
{
point[last[x]].next=t;
point[t].w=s[x];
last[x]=t;
}
q=x;
m=t-b[x]+1;
while (m-(s[x]-point[b[x]].w+1)>k)
{
b[x]=point[b[x]].next;
m=t-b[x]+1;
} www.2cto.com
if (s[x]-point[b[x]].w+1>ans) ans=s[x]-point[b[x]].w+1;
}
printf("%d\n",ans);
return 0;
}
