原题大意

每架飞机有早晚起降两种方式，给定n架飞机两种方式的起落时间，为每架飞机安排起落时间（早或晚），使得所有飞机起降时间按照早到晚的顺序之间的间隔时间最小值尽量大。

算法分析

最小时间尽量大应该采用二分的方法比较好，然后就变成了判别某个时间间隔m是不是符合要求的了。为没加飞机设立一个变量xi，0表示早，1表示晚，然后每架飞机i用两个点2i,2i+1表示，前者如果被标记表示早，后者被标记表示晚降。然后对不同的飞机的起降时间中间隔小于m的i，j建立约束条件，例如：i架飞机早降间隔和j架飞机的早降时间间隔小于m，那么约束条件就可以在图中这样表示：建立两条边2i—>2j+1, 2j->2i+1，表示如果i早降则j必须晚降，j早降i必须晚降。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e3+5;
struct TwoSAT{
    int n;
    vector<int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2], c;
    bool dfs(int x){
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x] = true;
        S[c++] = x;
        for(int i = 0; i < G[x].size(); i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }
    void init(int n){
        this->n = n;
        for(int i = 0; i < n * 2; i++) G[i].clear();
        mem(mark,false);
    }
    void add_clause(int x, int xval, int y, int yval){
        x = x * 2 + xval;
        y = y * 2 + yval;
        G[x^1].pb(y);
        G[y^1].pb(x);
    }
    bool solve(){
        for(int i = 0; i < n * 2; i+=2)
            if(!mark[i] && !mark[i+1]){
                c = 0;
                if(!dfs(i)){
                    while(c > 0) mark[S[--c]] = false;
                    if(!dfs(i+1)) return false;
                }
            }
        return true;
    }
};
TwoSAT solver;
int n, T[maxn][2];
bool test(int diff){
    solver.init(n);
    for(int i = 0; i < n; i++) for(int a = 0; a < 2; a++)
        for(int j = i+1; j < n; j++) for(int b = 0; b < 2; b++)
            if(abs(T[i][a] - T[j][b]) < diff) solver.add_clause(i, a^1, j, b^1);
        return solver.solve();
        //return true;
}
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n && n){
        int l = 0, r = 0;
        for(int i = 0; i < n; i++)
            for(int a = 0; a < 2; a++){
                cin >> T[i][a];
                r = max(r, T[i][a]);
            }
        while(l < r){
            int m = l + (r-l+1)/2;
            if(test(m)) l = m;
            else r = m-1;
        }
        cout << l << "\n";
    }
    return 0;
}