洛谷P1686 挑战题解

题意：

桃花岛其实也没什么好玩的，黄蓉经常偷偷跑到江湖上与洪七公等人玩。于是，黄药师就经常想一些游戏与女儿玩，为了是把黄蓉留在身边，江湖险恶啊！

这次黄药师又想了一种模拟游戏，游戏是这样的：她把整个桃花岛划分成一个坐标系。游戏开始前，黄蓉站在平面坐标系的一个点上，而她的闺房在坐标系的另一个点上，任何时候，她可以从当前所在点跨一步达到她周围的上、下、左、右四个点，黄药师不断地说四个字“东（E）”、“南（S）”、“西（W）”、“北（N）”，则黄蓉就想象着不断地从一个点走到另一个点，直至到自己的闺房为止。

比如，黄蓉开始时站在A点，她的家在B点，黄药师连续说了一串：NNNENNWWWSSW，则走了如下一个线路。然后，黄药师会问黄蓉：中间有没有走“弯路”了？即有没有捷径好走？比如，下图中就有多条捷径，可以从C走NN而到E，或走WW直接到D。

注意：捷径必须是直线。

黄药师听说你是一个程序设计高手，就想请你编个程序帮他测测这个游戏的难度，以便改进游戏规则后再让黄蓉挑战。

你的任务是：找一条最短的捷径。

输入格式：

第一行是一个整数n（3<=n<=250000）表示黄药师所报出的字符串长度。

第二行是一个由N、E、S、W组成的字符串，都是大写字母且中间没有空格。

我们把游戏的起点记为0，把黄蓉的闺房（即游戏的终点）记为n，中间的每一个落脚点都依次标记一个自然数。

输出格式：

输出只有一行，由3个数字和1个字符组成，中间用1个空格隔开。

第1个数字表示最短捷径的长度。

第2个数字表示最短捷径的开始点。

第3个数字表示最短捷径的结束点。

最后一个字符表示最短捷径的方向（同样用N、E、S、W中的一个表示）。

如果最短捷径存在多个解，那么输出开始点标号最小的那一条。如果仍然有多个解，那么输出结束点标号最大的。数据保证一定存在满足条件的最短捷径。

~~听说题解全被hack了？然而我通过了hack。。。~~

不知道为什么要标省选/NOI-，我觉得这题就是个水水水的模拟。

根据题意，显然这个捷径满足 \(x_a=x_b\) 或 \(y_a=y_b\) ，\(a,b\) 分别为起点和终点。

那就按 \(x,y\) 分别排序扫一遍就好啦。谁把这题它放在贪心题单的？？！！！

时间复杂度 \(O(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5+15))

int n,d=INF,st,ed,o[N];
char to,s[N];
struct node{int x,y;} a[N];
node getpos(node pre,char c)
{
    switch(c)
    {
        case 'N' : ++pre.y; break;
        case 'S' : --pre.y; break;
        case 'W' : --pre.x; break;
        case 'E' : ++pre.x; break;
    }
    return pre;
}
int cmp1(int u,int v) 
{ return a[u].x == a[v].x ? a[u].y < a[v].y : a[u].x < a[v].x; }
int cmp2(int u,int v) 
{ return a[u].y == a[v].y ? a[u].x < a[v].x : a[u].y < a[v].y; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s+1);
    a[0] = {0,0};
    for(int i=1; i<=n; i++) { a[i] = getpos(a[i-1], s[i]); o[i] = i; }
    sort(o, o+1+n, cmp1);
    for(int i=0; i<n; i++)
    {
        if(a[o[i]].x != a[o[i+1]].x || abs(o[i] - o[i+1]) == 1) continue;
        int _d = a[o[i+1]].y - a[o[i]].y, _st,_ed; char _to;
        o[i] < o[i+1] ? (_st=o[i], _ed=o[i+1], _to='N') : (_st=o[i+1], _ed=o[i], _to='S');
        if(_d < d || _d == d && _st < st || _d == d && _st == st && _ed > ed)
            d = _d, st = _st, ed = _ed, to = _to;
    }
    sort(o, o+1+n, cmp2);
    for(int i=0; i<n; i++)
    {
        if(a[o[i]].y != a[o[i+1]].y || abs(o[i] - o[i+1]) == 1) continue;
        int _d = a[o[i+1]].x - a[o[i]].x, _st,_ed; char _to;
        o[i] < o[i+1] ? (_st=o[i], _ed=o[i+1], _to='E') : (_st=o[i+1], _ed=o[i], _to='W');
        if(_d < d || _d == d && _st < st || _d == d && _st == st && _ed > ed)
            d = _d, st = _st, ed = _ed, to = _to;
    }
    cout << d << ' ' << st << ' ' << ed << ' ' << to << '\n';
    return 0;
}