题意：大致就是 一串数字中删除k个，是剩下的串中连续数字最长，输出长度
贴两个别人的代码，加了注释
[cpp]
/*
*/
#include
#include
#include
#include
#include
#include
#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
#include
#include
#include
#include
#include
#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
#include
#include
#include
#include
#include
#include
#include
#include