题意：
𝑅𝑒𝑘𝑖是一名狙击手，凭借肉眼视觉可以做到精确命中绝对半径2051公尺的一切目标。
作为一名优秀的狙击手，𝑅𝑒𝑘𝑖不仅经常保养枪支，也经常保养弹药。
𝑅𝑒𝑘𝑖有𝑛枚子弹，第𝑖枚的型号为𝐶𝑖，𝑅𝑒𝑘𝑖打算扔掉其中最多𝑘枚。
大多数优秀的狙击手都有艺术癖好，𝑅𝑒𝑘𝑖希望扔掉一部分子弹后，最
长的连续相同子弹序列的长度尽量长。
思路：
两种解法，二分或者双指针，其实很多题目能用其中一种另外一种都行，因为都要符合单调性，看到c的范围应该不难想到需要离散化，这里可以用map也可以手动哈希，算区间长度的时候比较绕，并且我都用的二维vector存他们的下标，理清楚还是好题的。
二分解法：
#include<bits/stdc++.h> #include<unordered_map> using namespace std; const int maxn=1e5+1000; unordered_map<int,int >mo; vector<int>edges[maxn]; int c[maxn]; int n,k; int main() { int i,j; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n>>k; int cnt=1; for(i=1; i<=n; i++) { cin>>c[i]; if(mo[c[i]]==0) { mo[c[i]]=cnt++; } edges[mo[c[i]]].push_back(i); } int ans=1,l,d1,r,max1,mid,s; for(auto x:mo) { d1=x.second,max1=0; if(edges[d1].size()<ans) continue; for(i=0; i<edges[d1].size(); i++) { l=i,r=edges[d1].size()-1,s=0; while(l<r) { mid=l+r+1>>1; if(edges[d1][mid]-edges[d1][i]+1-(mid-i+1)<=k) { l=mid; } else { r=mid-1; } } max1=max(max1,l-i+1); } ans=max(ans,max1); } cout<<ans; return 0; } /* ....... 首先离散化 用map每个出现的数字的下标都存一下 接下来我二分去寻找一下每个数字出现的最高次数 */
双指针：
因为手玩出问题了，整了两种写法，第二种参考了一下知乎某佬的，其实都是双指针看哪种好理解点吧。
我自己的：
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+1000; map<int,int >mo; vector<int>edges[maxn]; int c[maxn]; int n,k; int main() { int i,j; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>k; int cnt=1; for(i=1; i<=n; i++) { cin>>c[i]; if(mo[c[i]]==0) { mo[c[i]]=cnt++; } edges[mo[c[i]]].push_back(i); } int ans=1; for(auto x:mo) { int j=0,cnt=k,max1=0,d1=x.second; if(edges[d1].size()<=1) continue; for(i=0; i<edges[d1].size()-1; i++) { if(i>j) j=i; while(j<edges[d1].size()-1&&cnt>=edges[d1][j+1]-edges[d1][j]-1) { cnt-=(edges[d1][j+1]-edges[d1][j]-1); j++; } max1=max(max1,j-i+1); cnt+=(edges[d1][i+1]-edges[d1][i]-1); } ans=max(ans,max1); } cout<<ans<<endl; return 0; }
某巨佬的：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+1000; map<int,int >mo; vector<int> edges[100010]; int c[100010]; int n,k; int main() { int i,j; cin>>n>>k; int cnt=1; for(i=1; i<=n; i++) { cin>>c[i]; if(mo[c[i]]==0) { mo[c[i]]=cnt;cnt++; } edges[mo[c[i]]].push_back(i); } int ans=1; for(auto x:mo) { if(edges[x.second].size()<=1) continue; int cnt=k,max1=0,d1=x.second,l=0,r=0; while(l<=r&&r<edges[d1].size()-1) { if(cnt>=edges[d1][r+1]-edges[d1][r]-1) { cnt-=edges[d1][r+1]-edges[d1][r]-1; r++; } else{ l++; cnt+=edges[d1][l]-edges[d1][l-1]-1; } max1=max(max1,r-l+1); } ans=max(ans,max1); } cout<<ans<<endl; return 0; }
