題目
https://www.nowcoder.com/acm/contest/13/E
題目大意
最多可以拋掉k個(gè)數(shù)揉阎，求連續(xù)相同數(shù)字序列最長。
算法思路
- 對(duì)不同的數(shù)字枚舉输钩；對(duì)相同的數(shù)字床玻，采用雙指針的思想。如果需要拋掉的個(gè)數(shù)大于k屑柔，則記錄極值屡萤，左指針右移；否則掸宛，右指針右移死陆。
- 需要對(duì)數(shù)字進(jìn)行處理。由于數(shù)字范圍有1e9唧瘾，而n只有1e5措译，所以需要對(duì)數(shù)字進(jìn)行hash。然后開一個(gè)vector數(shù)組劈愚，將相同的數(shù)字的序號(hào)push到一個(gè)vector里面瞳遍，方便后面計(jì)算。
具體操作如下
map<int,int>id;
vector<int>pos[100010];
for(int i=0;i<n;i++){
cin>>a[i];
id[a[i]]=0;
}
int tot=0;
map<int,int>::iterator it;
for(it=id.begin();it!=id.end();it++)
it->second=++tot;//利用map來hash
for(int i=0;i<n;i++) a[i]=id[a[i]];//a[i]改存長度編號(hào)
for(int i=0;i<n;i++){
pos[a[i]].push_back(i);
}
代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<int,int>id;
vector<int>pos[100010];
int a[100010];
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,k;
while(cin>>n>>k){
for(int i=0;i<n;i++){
cin>>a[i];
id[a[i]]=0;
}
int tot=0;
map<int,int>::iterator it;
for(it=id.begin();it!=id.end();it++)
it->second=++tot;
for(int i=0;i<n;i++) a[i]=id[a[i]];
for(int i=0;i<n;i++){
pos[a[i]].push_back(i);
}
int ans=0;
for(int i=0;i<n;i++){
int s=0;
int j=1;int jishu=1;int cnt=0;
while(j<pos[i].size()){
while(cnt<=k&&j<pos[i].size()){
cnt+=pos[i][j]-pos[i][j-1]-1;
jishu++;
j++;
}
if(cnt>k) {
cnt-=pos[i][s+1]-pos[i][s]-1;
jishu--;
s++;
}
ans=max(ans,jishu);
}
}
cout<<ans<<endl;
}
return 0;
}
廢話
開始的時(shí)候想到要對(duì)于數(shù)列進(jìn)行處理菌羽。但沒有想到將同樣的數(shù)字分為一組進(jìn)行處理掠械。之前想的做法大概是對(duì)于每個(gè)位置的數(shù)以其為開頭，最多能連多少注祖』伲可想而知，這樣復(fù)雜度就很高了是晨。
