UVALive3211

发表于 | 分类于 |

题目传送门

Description

有$N$架飞机，每架飞机有两个时间可以降落，一早一晚。

现在给出每架飞机可以降落的两个时间，问所有相邻时间降落的飞机中的最小时间间隔最大是多少。

多组测试数据。

Input

每组测试数据：

第一行：一个整数$N$表示飞机数。

接下来$N$行：每行两个整数$e$、$l$表示早的时间和晚的时间（别问我为什么时间长这样）。

Output

几个数据就几行：每行一个整数，最小时间间隔的最大。

Solution

最小求最大，二分。

所以每次二分一个时间$T$，然后2-SAT连边：若$A$飞机早的那个时间$A_1$与$B$飞机早的那个时间$B_1$的间隔小于$T$，就把$A_1$与$B_2$连边从$A_1$指向$B_2$，同理也要连$B_1\rightarrow A_2$。

然后跑$dfs​$看是否存在合法方案，是否可行。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define INF 1000000000
//#include<>
using namespace std;
struct Fl
{
	int x1,x2; 
}F[2100];
int n,R,L;
struct EDGE
{
	int ap;
	EDGE *next;
}edge[21000000],*ind[2100*2];
int el;
int S[2100*2],sl;
bool chose[2100*2];
void add_edge(int x,int y)
{
	edge[++el].ap=y;
	edge[el].next=ind[x];
	ind[x]=&edge[el];
}
void init()
{
	for(int i=0;i<=4100;i++) ind[i]=NULL,S[i]=0,chose[i]=0;
	el=sl=0;
}
void build(int x){
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(abs(F[i].x1-F[j].x1)<x) add_edge(i*2,j*2+1),add_edge(j*2,i*2+1);
			if(abs(F[i].x1-F[j].x2)<x) add_edge(i*2,j*2),add_edge(j*2+1,i*2+1);
			if(abs(F[i].x2-F[j].x1)<x) add_edge(i*2+1,j*2+1),add_edge(j*2,i*2);
			if(abs(F[i].x2-F[j].x2)<x) add_edge(i*2+1,j*2),add_edge(j*2+1,i*2);
		}
	}
}
bool dfs(int x)
{
	bool asd=1;
	if(chose[x^1]) return 0;
	if(chose[x]) return 1;
	chose[x]=1;
	S[++sl]=x;
	for(EDGE *k=ind[x];k!=NULL;k=k->next){
		if(!dfs(k->ap)) asd=0;
		if(asd==0)
		{
			return 0;
		}
	}
	return 1;
}
bool check(int N)
{
	init();
	build(N);
	for(int i=0;i<n;i++)
	{
		if(!chose[i*2+1]&&!chose[i*2])
		{
			sl=0;
			if(!dfs(i*2+1)){
				while(sl) chose[S[sl--]]=0;
				if(!dfs(i*2)) return 0;
			}
		}
	}
	return 1;
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		L=1,R=0;
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&F[i].x1,&F[i].x2);
			R=max(L,max(F[i].x1,F[i].x2));
		}
		R++;
		while(L<R-1)
		{
			int mid=(L+R)/2;
			if(!check(mid)) R=mid;
			else L=mid;
		}
		printf("%d\n",L);
	}
	return 0;
}