CodeForces Round #116 (180E) - Cubes

第一次做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; 
}