蓝书325页的基础题
二分+2-sat
//看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#includeusing namespace std;#pragma comment(linker,"/STACK:102400000,102400000")#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const int maxn = 5000 + 5;struct TwoSAT{ int n; vector G[maxn]; bool mark[maxn]; int c, s[maxn];///c是表示目前dfs到的个数和已经被标记的集合s 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 < 2 * n; i++) G[i].clear(); memset(mark, 0, sizeof(mark)); } void add_edge(int x, int xval, int y, int yval){ x = x * 2 + xval, y = y * 2 + yval; G[x ^ 1].push_back(y); G[y ^ 1].push_back(x); } bool solve(){ for (int i = 0; i < 2 * n; i += 2){ if (!mark[i] && !mark[i + 1]){ c = 0; if (!dfs(i)){ while (c) mark[s[--c]] = false; if (!dfs(i + 1)) return false; } } } return true; }};TwoSAT sat;int n;int E[maxn], L[maxn];int ti[maxn][2];bool test(int p){ sat.init(n); for (int i = 0; i < n; i++){ for (int x = 0; x < 2; x++){ for (int j = i + 1; j < n; j++){ for (int y = 0; y < 2; y++){ if (abs(ti[i][x] - ti[j][y]) < p){ ///那就说明不成立，因此要建立成立的边 sat.add_edge(i, x ^ 1, j, y ^ 1); } } } } } return sat.solve();}int main(){ while (scanf("%d", &n) == 1){ int lb = 0, rb = 0; for (int i = 0; i < n; i++){ scanf("%d%d", E + i, L + i); ti[i][0] = E[i], ti[i][1] = L[i]; rb = max(rb, max(E[i], L[i])); } rb++; while (lb < rb - 1){ int mid = (lb + rb) / 2; if (test(mid)) lb = mid; else rb = mid; } printf("%d\n",lb); } return 0;}