投稿
  1. 首页
  2. C

英语作文

code • 2022-4-11 • C • 阅读 67

英语作文,第1张

原题链接 题目描述

在写英语作文的时候，两个相同单词靠的太近肯定不好。


现在 ZHR 给了你一段n个单词的英文，问你有多少对相同单词中间间隔的单词数小于等于k 。


输入描述：
第一行两个整数，为n 和 k 。


第二行nnn个由仅小写字母组成的单词。


每个单词长度小于等于10 。


1

输出描述:

一行一个正整数，表示有多少对单词中间间隔的单词数小于等于k。


示例1

输入

11 2
i love you you love mi mixue ice cream and tea

输出

2

说明

只有 you 和 love 两个单词间隔的单词数小于等于2

首先最简单的思路就是两个for循环，但是肯定会超时。


看到string和数字，可以用map起来。


接下来遍历字联系符串数组，每一次让mp[str[i]]++,表示字符串str[i]出现的次数加一（为了对后面的单词做计算），然后对一个区间k+1进行 *** 作，因为第k-i-1个字符串下一个循环就要离开这个区间，所以令mp[str[i-i-1]]--。


每一次循环的开始变对mp[str[i]]求和，表示字符串单词间隔小于等于k的个数。


C++AC代码 

#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+10;
long long ans;
string a[maxn];
mapmp;
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		ans+=mp[a[i]];
		mp[a[i]]++;
		if(i>=k+1) mp[a[i-k-1]]--;
	}
	cout<

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/577976.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-11
下一篇 2022-04-11

发表评论

登录后才能评论

评论列表（0条）

保存