每架飞机只能在E L 这2个时间点降落 每2架并且降落的时间间隔必须大于等于p才算安全 目标使p尽量大
二分时间间隔 做2-SAT 有解说明可行
xi = true 表示选择E false 选择L
如果 abs(Ei - Ej) < p (p 是当前二分到的值) 那么 1.选择了Ei 必须选择Lj 2.选择了Ej 必须选择Li
建图 上模版
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int maxn = 2010; vector <int> G[maxn*2]; int n, T[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() { for(int i = 0; i < n*2; i++) G[i].clear(); memset(mark, 0, sizeof(mark)); } void add_clause(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 < 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; } bool test(int diff) { init(); 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) add_clause(i, a^1, j, b^1); } } } } return solve(); } int main() { while(scanf("%d", &n) == 1) { int L = 0, R = 0; for(int i = 0; i < n; i++) for(int a = 0; a < 2; a++) { scanf("%d", &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; } printf("%d\n", L); } return 0; }