HDU 5699 貨物運輸

Problem Description

公元2222年，l國發生了一場戰争。

小Y負責上司勞工運輸物資。

其中有

m種物資的運輸方案，每種運輸方案形如

li,ri。表示存在一種貨物從

li運到

ri。

這裡有

n個城市，第

i個城市與第

i+1個城市相連（這裡

1号城市和

n号城市并不相連），并且從

i号城市走到

i+1号或者從

i+1号走到

i号需要耗費1點時間。

由于高科技的存在，小Y想到了一種節省時間的好方案。在X号城市與Y号城市之間設立傳送站，隻要這麼做，在X号城市走到Y号城市不需要耗費時間，同樣的，從Y号城市走到X号城市也不需要耗費時間。

但是為了防止混亂，隻能設立這麼一條傳送站。

現在這些運輸方案同時進行，小Y想讓最後到達目的地的運輸方案時間最短。

在樣例中，存在兩條運輸方案，分别是1号城市到3号與2号到4号，那麼我們在2号城市與3号城市建立傳送站，這樣運輸方案時間最長的隻需要1點時間就可以了。

Input

多組測試資料

第一行兩個整數

n,m(1≤n,m≤1000000)。

接下來

m行，每行兩個整數

li,ri(1≤li,ri≤n)。（若

li=ri，則不需要耗費任何時間）

Output

一個數表示答案。

Sample Input

5 2

1 3

2 4

Sample Output

1

二分答案加驗證，驗證的方法比較巧妙，想了挺久才搞懂。

二分答案為最遠的距離d，用這個d來驗證，對于原本距離小于d的可以不用考慮了，隻考慮原來大于d的

假設大于d的距離的兩端是L和R，那麼我們選擇建的區間是l,r那麼一定要滿足

abs(l-L)+abs(r-R)<=d

把這個式子的絕對值去掉，我們可以得到四條式子。

l-L+r-R<=d;

l-L-r+R<=d;

L-l+r-R<=d;

L-l+R-r<=d;

整理一下可得 L+R-d<=l+r<=L+R+d,L-R-d<=l-r<=L-R+d;

那麼我們就可以知道l+r和l-r的範圍了，然後隻要做區間的合并，

看最後是否有合法的l+r和l-r即可。

這裡需要注意一個問題，當l+r和l-r是唯一的且相加為奇數，那麼這樣的情況下，l和r是不存在的。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef __int64 LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
int n, L[maxn], R[maxn], m;

bool check(int d)
{
  int l = -2 * n, ll = -2 * n;
  int r = 3 * n, rr = 3 * n;
  for (int i = 1; i <= m; i++)
  {
    if (R[i] - L[i] <= d) continue;
    l = max(l, L[i] + R[i] - d);
    r = min(r, L[i] + R[i] + d);
    ll = max(ll, L[i] - R[i] - d);
    rr = min(rr, L[i] - R[i] + d);
  }
  return l == r&&ll == rr ? !(l + ll & 1) : l <= r&&ll <= rr;
}

int main()
{
  while (scanf("%d%d", &n, &m) != EOF)
  {
    for (int i = 1; i <= m; i++)
    {
      scanf("%d%d", &L[i], &R[i]);
      if (L[i] > R[i]) swap(L[i], R[i]);
    }
    int q = 0, h = n;
    while (q <= h)
    {
      int mid = q + h >> 1;
      if (check(mid)) h = mid - 1; else q = mid + 1;
    }
    printf("%d\n", q);
  }
  return 0;
}