小白月赛-英语作文

链接：https://ac.nowcoder.com/acm/contest/11223/C 来源：牛客网

题目描述

在写英语作文的时候，两个相同单词靠的太近肯定不好。现在 ZHR 给了你一段nn个单词的英文，问你有多少对相同单词中间间隔的单词数小于等于kk 。

输入描述:

第一行两个整数，为nn 和 kk 。

第二行nn个由仅小写字母组成的单词。每个单词长度小于等于1010 。

输出描述:

一行一个正整数，表示有多少对单词中间间隔的单词数小于等于kk 。 示例1 输入

11 2 i love you you love mi mixue ice cream and tea 输出 复制 2 说明 只有 you 和 love 两个单词间隔的单词数小于等于22

using namespace std;
const int N = 100010;
int n,k;
string s;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    long long  ans = 0;
    unordered_map<string,vector<int>>p;
    for(int  i=1;i<=n;++i){
        cin>>s;
        auto &v=p[s];
        ans+=v.end()-lower_bound(v.begin(),v.end(),i-k-1);
        v.push_back(i);
    }
    cout<<ans;
}