绝对半径2051（尺度法）

题目

https://www.nowcoder.com/acm/contest/13/E

题目大意

最多可以抛掉k个数，求连续相同数字序列最长。

算法思路

• 对不同的数字枚举；对相同的数字，采用双指针的思想。如果需要抛掉的个数大于k，则记录极值，左指针右移；否则，右指针右移。
• 需要对数字进行处理。由于数字范围有1e9，而n只有1e5，所以需要对数字进行hash。然后开一个vector数组，将相同的数字的序号push到一个vector里面，方便后面计算。
  具体操作如下

 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]改存长度编号
    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;
}

废话

开始的时候想到要对于数列进行处理。但没有想到将同样的数字分为一组进行处理。之前想的做法大概是对于每个位置的数以其为开头，最多能连多少。可想而知，这样复杂度就很高了。