UVALive 3211 Now or later
2024-10-16 09:45:17
每架飞机有早晚起降两种方式,给定n架飞机两种方式的起落时间,为每架飞机安排起落时间(早或晚),使得所有飞机起降时间按照早到晚的顺序之间的间隔时间最小值尽量大。
分析:
最小时间尽量大应该采用二分的方法比较好,然后就变成了判别某个时间间隔m是不是符合要求的了。为没加飞机设立一个变量xi,0表示早,1表示晚,然后每架飞机i用两个点2*i,2*i+1表示,前者如果被标记表示早,后者被标记表示晚降。 然后对不同的飞机的起降时间中间隔小于m的i,j建立约束条件,例如:i架飞机早降间隔和j架飞机的早降时间间隔小于m,那么约束条件就可以在图中这样表示:建立两条边2*i—>2*j+1, 2*j->2*i+1,表示如果i早降则j必须晚降,j早降i必须晚降。
代码:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define pb push_back
#define mp(a, b) make_pair((a), (b))
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define stop system("pause");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define pragma comment(linker, "/STACK:102400000, 102400000")
#define inf 0x0f0f0f0f using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii,int> VII;
typedef vector<int>:: iterator IT;
const int maxn = 2222;
int E[maxn*2];
struct TwoSAT
{
int n, mark[maxn*2], S[maxn*2];
VI g[maxn*2];
int c;
void init(int n)
{
this->n = n;
for(int i = 0; i < maxn*2; i++)
g[i].clear();
memset(mark, 0, sizeof(mark));
}
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 add_clause(int x, int xval, int y, int yval)
{
x = 2*x+xval;
y = 2*y+yval;
g[x^1].pb(y);
g[y^1].pb(x);
}
bool solve(void)
{
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;
}
} Sat;
int main(void)
{
int n;
while(~scanf("%d", &n))
{
int l = inf, r = 0, m;
for(int i = 1; i <= n; i++)
{
scanf("%d%d", E+2*i-2, E+2*i-1);
l = min(l, min(E[2*i-2], E[2*i-1]));
r = max(r, max(E[2*i-2], E[2*i-1]));
}
r= r-l+1;
l = 0;
while(l < r - 1)
{
m = (l+r)>>1;
Sat.init(n);
for(int x = 0; x < n; x++)
for(int y = x+1; y < n; y++)
for(int xval = 0; xval < 2; xval++)
for(int yval = 0; yval < 2; yval++)
if(abs(E[2*x+xval] - E[2*y+yval]) < m)
{
Sat.add_clause(x, 1-xval, y, 1-yval);
}
if(!Sat.solve())
r = m;
else l = m;
}
printf("%d\n", l);
}
return 0;
}
最新文章
- ip扫描
- css体验优化之图片容器设置宽高比
- debian开机启动管理
- int 与Integer的用法与区别
- Unieap3.5-禁用Form表单中的全部标签
- Optimistic Offline Lock乐观离线锁
- jquery如何实现domReady和onload判断的
- XMPP的Stanzas
- linux下sqlite3可视化工具
- 简单CSS定位瀑布流实现方法
- tomcat的JK和JK2
- LeetCode OJ 78. Subsets
- jdk8 之 java.time包AND DateUtils
- Viso设置背景
- 每天一个linux命令(37)--iostat命令
- Oracle报错ORA-16433非归档丢失redo无法启动的恢复过程
- python----函数初识
- Python学习(七) —— 装饰器、迭代器、生成器
- 更换JDK版本时的问题:Error: could not open `C:\Java\jre7\lib\amd64\jvm.cfg&#39;
- MySQL连接、登录、密码等