题意：几个人想做好朋友，朋友之间相差位置小于等于k，且长度相同
分析；排序，将长度相同的放在一起。若长度相同，第i个人能放进去的条件是位置相差下雨等于k。
若不能放进去，将对头踢掉，踢到对头是第i个人的朋友的时候为止。若长度不相同，则将队列清空。
更新sum值，在第i个人进去的时候就加上队列的当前长度。
这个没考虑的问题是当长度相同，但是队列中的人都不符合其位置差，全部剔除的时候，第i个人却没有加进队列，导致错误
//
Problem#: 8842
//
Submission#: 2269282
//
The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
//
URI:
http://creativecommons.org/licenses/by-nc-sa/3.0/
//
All Copyright reserved by Informatic Lab of Sun Yat-sen University
//
Problem#: 8842
//
Submission#: 2269196
//
The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
//
URI:
http://creativecommons.org/licenses/by-nc-sa/3.0/
//
All Copyright reserved by Informatic Lab of Sun Yat-sen University
/*
#include<stdio.h>
#include<string.h>
const int MN=110;
int vis[MN][MN];
char str[MN][MN];
int n,m;
int A,B,C,D,E;
int row[]= {-1,1,0,0};
int col[]= {0,0,-1,1};
int num1[200];
int num2[200];
struct Node
{
int x,y;
} s,e;
void DFS(int x,int y,char flag)
{
for(int i=0; i<4; i++)
{
int xx=x+row[i];
int yy=y+col[i];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && str[xx][yy]!='X' && vis[xx][yy]==0)
{
if(str[xx][yy]==flag)
{
num2[flag]++;
}
}
}
}
void work(int i,int j)
{
if(str[i][j]=='S')
{
s.x=i;
s.y=j;
}
else if(str[i][j]=='G')
{
e.x=i;
e.y=j;
}
num1[str[i][j]]++;
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m))
{
A=B=C=D=E=0;
for(i=1; i<=n; i++)
{
scanf("%s",str[i]+1);
for(j=1; j<=m; j++)
{
work(i,j);
}
}
for(char t='a'; t<='e'; t++)
{
DFS(s.x,s.y,t);
if(num2[t]==num1[t])
{
DFS2()
}
}
}
return 0;
}
*/
#include
<stdio.h>
#include
<algorithm>
#include
<
string
.h>
#include
<queue>
using
namespace
std;
#define
LL long long
const
int
MN=
300010
;
struct
Node
{
char
nam[
30
];
int
len;
int
pos;
} node[MN];
queue
<
int
>
Q;
bool
cmp(Node a,Node b)
{
if
(a.len!=b.len)
return
a.len<
b.len;
return
a.pos<
b.pos;
}
int
main()
{
int
n,k,i,j;
int
ans;
while
(scanf(
"
%d%d
"
,&n,&k)!=
EOF)
{
getchar();
while
(!
Q.empty()) Q.pop();
for
(i=
1
; i<=n; i++
)
{
gets(node[i].nam);
node[i].len
=
strlen(node[i].nam);
node[i].pos
=
i;
}
sort(node
+
1
,node+n+
1
,cmp);
long
long
sum=
0
;
int
length=
1
;
Q.push(
1
);
int
t;
for
(i=
2
; i<=n; i++
)
{
t
=
Q.front();
if
(node[t].len!=
node[i].len)
{
while
(!
Q.empty()) Q.pop();
length
=
1
;
Q.push(i);
}
else
{
if
(node[i].pos-node[t].pos<=
k)
{
Q.push(i);
sum
+=
length;
length
++
;
}
else
{
while
(!
Q.empty())
{
t
=
Q.front();
if
(node[i].pos-node[t].pos<=
k)
{
Q.push(i);
sum
+=
length;
length
++
;
break
;
}
else
{
Q.pop();
length
--
;
if
(Q.empty())
{
Q.push(i);
length
=
1
;
break
;
}
}
}
}
}
}
printf(
"
%lld\n
"
,sum);
}
return
0
;
}
