自动搬运

查看原文

来自洛谷，原作者为

	panjidongc **

搬运于2025-08-24 22:32:49，当前版本为作者最后更新于2021-08-12 00:12:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 只有英文名长度相同的才能成为好朋友，所以名字是由哪些字母组成的并不重要，我们只需记录下名字长度即可。

• 我们观察到数据中英文名的长度很小，于是我们可以对每一种长度的名字数量做前缀和，之后扫描一遍，统计排名在 $k$ 名之内的学生组数即可，时间复杂度 $O(n)$。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int N=300005;
typedef long long ll;

char s[25];
int a[N],b[25][N]; //a[]是每个人的名字长度，b[i][]是名字长度为i的名字数量前缀和
int n,k;
ll ans;

int main()
{
	int i,j;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%s",s);
		a[i]=strlen(s);
	}
	for(i=2;i<=20;i++)
		for(j=1;j<=n;j++)
		{
			b[i][j]=b[i][j-1];
			if(a[j]==i)
				b[i][j]++;
		} //求前缀和
	for(i=1;i<=n;i++) //第i名最远只能和第i+k名做好朋友
	{
		if(i+k<n)
			ans+=(ll)b[a[i]][i+k]-b[a[i]][i];
		else //注意排名靠后的几个人最远只能和最后一名做好朋友
			ans+=(ll)b[a[i]][n]-b[a[i]][i];
	}
	printf("%lld\n",ans);
	return 0;
}