本文共 799 字,大约阅读时间需要 2 分钟。
【】
【题目大意】
有n架飞机要着陆, 每架飞机都可以选择“早着陆”或者“晚着陆”中的一种,不能在其他时间着陆。 给出每架飞机“早着陆”和“玩着陆”的时间, 问怎样安排着陆,才可以使得着任意两架飞机的陆时间间隔最小,输出最小值。
【思路】
水题,二分最小间隔时间,用2-SAT判断。
【代码】
#include#include #include #include #include using namespace std;const int MAXN = 2005;const int VN = MAXN*2;const int EN = MAXN*MAXN*4;int n, m;int t[MAXN][2];struct Graph{ int size, head[VN]; struct{int v, next; }E[EN]; void init(){size=0; memset(head, -1, sizeof(head));} void addEdge(int u, int v){ E[size].v = v; E[size].next = head[u]; head[u] = size++; }}g;class Two_Sat{public: bool check(){ scc(); for(int i=0; i >1; buildGraph(mid); if(sat.check()){ ans = mid; l = mid+1; }else r = mid; } printf("%d\n", ans); } return 0;}
转载地址:http://apzni.baihongyu.com/