昨天第一次做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:
#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;
}
if (s[x]-point[b[x]].w+1>ans) ans=s[x]-point[b[x]].w+1;
}
printf("%d\n",ans);
return 0;
}