題意：幾個人想做好朋友，朋友之間相差位置小于等于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
;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
