p1763.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 250001;
struct point{ int x,y,s; };
point a[MAXN];
bool cmpx(point a,point b){ return a.x < b.x || a.x == b.x && a.y < b.y; }
bool cmpy(point a,point b){ return a.y < b.y || a.y == b.y && a.x < b.x; }
int main(){
    char c;
    int n;
    cin >> n;
    getchar();
    a[0].x = a[0].y = a[0].s = 0;
    for(int i = 1;i <= n;++i){
        scanf("%c",&c);
        a[i].s = i;
        switch(c){
            case 'N':a[i].x = a[i-1].x; a[i].y = a[i-1].y + 1; break;
            case 'S':a[i].x = a[i-1].x; a[i].y = a[i-1].y - 1; break;
            case 'W':a[i].x = a[i-1].x - 1; a[i].y = a[i-1].y; break;
            case 'E':a[i].x = a[i-1].x + 1; a[i].y = a[i-1].y; break;
        }
    }
    sort(a,a+n+1,cmpx);
    int i(1),ans = 1<<30,anss = MAXN,anse = 0;
    char ansd;
    while(i <= n){
      for(;i <= n && a[i].x == a[i-1].x;++i)
        if(a[i].y - a[i-1].y < abs(a[i].s - a[i-1].s)){
          if(a[i].y - a[i-1].y < ans){ 
            ans = a[i].y - a[i-1].y;
            anss = min(a[i].s,a[i-1].s);
            anse = max(a[i].s,a[i-1].s);
            if(a[i].s > a[i-1].s) ansd = 'N';
            else ansd = 'S';
          }
          else if(a[i].y - a[i-1].y == ans){
            int t1 = min(a[i].s,a[i-1].s),t2 = max(a[i].s,a[i-1].s);
            if(t1 < anss || t1 == anss && t2 > anse){
                anss = t1;
                anse = t2;
                if(a[i].s > a[i-1].s) ansd = 'N';
                else ansd = 'S';
            }
          }
        }
      ++i;
    }
    sort(a,a+n+1,cmpy);
    i = 1;
    while(i <= n){
      for(;i <= n && a[i].y == a[i-1].y;++i)
        if(a[i].x - a[i-1].x < abs(a[i].s - a[i-1].s)){
          if(a[i].x - a[i-1].x < ans){ 
            ans = a[i].x - a[i-1].x;
            anss = min(a[i].s,a[i-1].s);
            anse = max(a[i].s,a[i-1].s);
            if(a[i].s > a[i-1].s) ansd = 'E';
            else ansd = 'W';
          }
          else if(a[i].x - a[i-1].x == ans){
            int t1 = min(a[i].s,a[i-1].s),t2 = max(a[i].s,a[i-1].s);
            if(t1 < anss || t1 == anss && t2 > anse){
                anss = t1;
                anse = t2;
                if(a[i].s > a[i-1].s) ansd = 'E';
                else ansd = 'W';
            }
          }
        }
      ++i;
    }
    printf("%d %d %d %c\n",ans,anss,anse,ansd);
}