2013年8月21日

UVa 10874 - Segments

#include <cstdio>

inline int abs(int n) {
  return n < 0 ? -n : n;
}

inline int min(int a, int b) {
  return a < b ? a : b;
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    int p1 = 1, p2 = 1, s1 = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
      int l, r;
      scanf("%d%d", &l, &r);
      int d1 = min(s1 + abs(p1 - r) + abs(r - l), s2 + abs(p2 - r) + abs(r - l));
      int d2 = min(s1 + abs(p1 - l) + abs(l - r), s2 + abs(p2 - l) + abs(l - r));
      s1 = d1 + 1;
      s2 = d2 + 1;
      p1 = l;
      p2 = r;
    }
    printf("%d\n", min(s1 + abs(p1 - n), s2 + abs(p2 - n)) - 1);
  }
  return 0;
}

沒有留言:

張貼留言