NDK 1332 挑战
| 问题描述： | 桃花岛其实也没什么好玩的，黄蓉经常偷偷跑到江湖上与洪七公等人玩。于是，黄药师就 经常想一些游戏与女儿玩，为了是把黄蓉留在身边，江湖险恶啊！ 比如，黄蓉开始时站在A点，她的家在B点，黄药师连续说了一串： NNNENNWWWSSW，则走了如下一个线路。然后，黄药师会问黄蓉：中间有没有走“弯 路”了？即有没有捷径好走？比如，下图中就有多条捷径，可以从C走NN而到E，或走WW 直接到D。 | |
| 数据输入： | 第一行是一个整数n（ 3 <= n <= 250000）表示黄药师所报出的字符串长度。 | |
| 结果输出： | 输出只有一行，由3个数字和1个字符组成，中间用1个空格隔开。 | |
| 样例： | 12 NNNENNWWWSSW | 2 3 11 W |
| 核心思想： | 双快排，然后比较就好 | |
typeatp=recordx,y,num:longint;end;
vara:array[-2..250010]of atp;n,st,ed,t1,t2,ans:longint;ch:char;
//==============================================================
procedure init;
vari:longint;
beginfillchar(a,sizeof(a),0);readln(n);fori:=1 to n dobeginread(ch);a[i]:=a[i-1];a[i].num:=i;{<原位置>}case ch of'E':inc(a[i].y);{<求（x，y）坐标>}'W':dec(a[i].y);'N':inc(a[i].x);'S':dec(a[i].x);end;end;
end;
//==========================================================
procedure qsortx(l,r:longint);
vari,j:longint;k,t:atp;
begini:=l;j:=r;k:=a[(l+r)shr 1];repeatwhile (a[i].xk.x)or((a[j].x=k.x)and(a[j].y>k.y)) do dec(j);ifi<=j thenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;until i>j;ifil then qsortx(l,j);
end;
procedure qsorty(l,r:longint);
vari,j:longint;k,t:atp;
begini:=l;j:=r;k:=a[(l+r)shr 1];repeatwhile (a[i].yk.y)or((a[j].y=k.y)and(a[j].x>k.x)) do dec(j);ifi<=j thenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;until i>j;ifil then qsorty(l,j);
end;
//===========================================================
function pd(x,y,z:longint):boolean;{<按题目要求，先比长度再比开始点，最后比结束点>}
beginifxans then exit(false);ifst>y then exit(true);ifst}beginj:=a[i+1].y-a[i].y;{<列差即为路径长度>}if a[i].num}if pd(j,t1,t2) thenbeginans:=j;st:=t1;ed:=t2;ch:=ct;end;end;
end;
//=============================================================
procedure work2;
vari,j:longint;ct:char;
beginfori:=1 to n-1 doifa[i].y=a[i+1].y thenbeginj:=a[i+1].x-a[i].x;if a[i].num}qsorty(1,n);work2;{<竖着的捷径>}writeln(ans,' ',st,' ',ed,' ',ch);
end;
//============================================================
beginassign(input,'p1332.in');reset(input);assign(output,'p1332.out');rewrite(output);init;main;close(input);close(output);
end. 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！