C题:英语作文 (思想:二分查找)
最开始想用哈希表来着,但是后来写着写着嫌麻烦换了一种写法,但原理类似,都是将string转换成int类型,然后采用vector数组去存储。不同的字符串转换成不同的vector数组下标,转换的工作让map来完成。
在处理相同的单词时,使用二分查找寻找到最后一个满足距离差<=k+1的下标即可,时间复杂度O(nlogn)
#include<map>
#include<vector>
using namespace std;
#define N 100010
string s[N];
map<string,long long> m;
vector<long long> v[N];
int n,k;
int binsearch(int value,int hash,int low,int high){
int mid=(high+low)/2;
if(1+low==high){
if(value-v[hash][low]<=k+1) return low;
else return high;
}
else if(value-v[hash][mid]<=k+1){
return binsearch(value,hash,low,mid);
}
else{
return binsearch(value,hash,mid,high);
}
}
int main(){
cin>>n>>k;
int num=1;
for(int i=0;i<n;i++){
cin>>s[i];
if(!m[s[i]]){
m[s[i]]=num++;
}
}
long long cnt=0;
for(int i=0;i<n;i++){
int hash = m[s[i]];
if(v[hash].size()){
if(i-v[hash][v[hash].size()-1]<=k+1){
int mid=binsearch(i,hash,0,v[hash].size());
cnt+=v[hash].size()-mid;
}
}
v[hash].push_back(i);
}
cout<<cnt<<endl;
}
/*
10 2
a a a a a a a a a a
*/