題意：大致就是 一串數字中刪除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", &n, &m, &k);//
for (int i = 1; i <= n; i++)
{
scanf("%d", &c[i]);
V[c[i]].push_back(i);//把位置i放到他所在的顏色的隊列中
p[i] = V[c[i]].size()-1;//她是當前第幾個？
}
ans = 0;
for (s = 1; s <= n; s++)
{
r = c[s];
find(p[s], V[r].size()-1);//當前元素在隊列中的位置 最後一個的位置
}
printf("%d\n", ans);
return 0;
}
