题解 | #赢的次数#

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
*/