CodeForces 180E Cubes--后续指针--当前个数

题意：大致就是一串数字中删除k个，是剩下的串中连续数字最长，输出长度

贴两个别人的代码，加了注释

[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;//记录的是第一个x的位置
            last[x]=t;//记录这个这是第一个片段头的位置下面用来制造后续指针
            point[t].w=s[x];//记录他是第几个x     这个在算中间要删除都少个其他数字是很有用
        }else if (x!=q)//有祖先并且和上一个不相等这是一个新片段的开始
        {
            point[last[x]].next=t;//上一个片段头的后续指针指向这个新片段头
            point[t].w=s[x];//记录他是第几个
            last[x]=t;//更新
        }//有祖先并且上一个就是的情况无处理因为只记录一个片段的开始
        q=x;//更新记录

        //b[x]表示的是某片段头的位置也就是从这个开始算连续x
        m=t-b[x]+1;//从那个片段头到这儿的所有数字个数
        while (m-(s[x]-point[b[x]].w+1)>k)//括号里的是从那个片段头到这儿的x的个数做差就是需要删除数字的个数若>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;
}

*/
#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;//记录的是第一个x的位置
   last[x]=t;//记录这个这是第一个片段头的位置下面用来制造后续指针
   point[t].w=s[x];//记录他是第几个x     这个在算中间要删除都少个其他数字是很有用
  }else if (x!=q)//有祖先并且和上一个不相等这是一个新片段的开始
  {
   point[last[x]].next=t;//上一个片段头的后续指针指向这个新片段头
   point[t].w=s[x];//记录他是第几个
   last[x]=t;//更新
  }//有祖先并且上一个就是的情况无处理因为只记录一个片段的开始
  q=x;//更新记录

  //b[x]表示的是某片段头的位置也就是从这个开始算连续x
  m=t-b[x]+1;//从那个片段头到这儿的所有数字个数
  while (m-(s[x]-point[b[x]].w+1)>k)//括号里的是从那个片段头到这儿的x的个数做差就是需要删除数字的个数若>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;
}
[cpp]
?/*
把不同颜色的都筛选出来，记录原来的位置
同时要记录她是第几个

计算某区间内有多少需要删除时：所有元素个数-这段里这个颜色的个数

*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int MAXN = 200000+5, MAXM = 100000+5;
const int MAXH = 1000007;
int n, m, k, c[MAXN];
int s, r, ans, p[MAXN];
vector<int> V[MAXM];
void find(int x, int y)
{
    int mid = (x+y)>>1;
    int z = (V[r][mid]-s)-(mid-p[s]);//一直是在跟s计算    z是需要删除的个数
    if (z <= k)
    {
        ans = max(ans, mid-p[s]+1);
        if (x != y)
            find(mid+1, y);
    }
    else
    {
        if (x != y)
            find(x, mid);
    }
}
int main()
{
    scanf("%d%d%d"

补充：软件开发 , C++ ,