雀士分组（二分图染色 + 二分）

题目链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4532.html

题目大意：

sdut雀士联盟中有许多水平各异的职业雀士，现在为了参加即将举办的神仙杯麻将比赛，联盟决定将所有雀士分为两队（碰精队和杠精队）分开举行训练赛。为了方便分组，联盟对每一位选手进行了雀力评估，对第i个雀士的评估得分为Ai。联盟出于对于雀士的心态考虑决定将实力相近的雀士分为一组，即让max（碰精队max - 碰精队min，杠精队max - 杠精队min）的值最小（其中碰精队max代表碰精队中最高那位的雀力数值，其他同理）。不过联盟中部分雀士由于打法原因和一些其他雀士关系恶劣，绝对不能分在一组之内。分组方案的结果可以使一组人的人数为 0。

Input

第一行一个N（1 <= N <= 100000）代表联盟中一共有N名雀士，雀士编号由1至N。
第二行输入N个整数Ai（1 <= Ai <= 100000000），代表第i名雀士雀力评估得分。
接下来输入1个整数M（0 <= M <= 100000），代表有M组雀士关系恶劣，不能分进同一组。
接下来输入M行x, y（1 <= x, y <= N），代表编号为x的和编号为y的雀士关系恶劣，保证不会重复输入雀士关系。

Output

假如没有办法将所有的雀士分成两队，输出 “impossible”(输出不包括引号)，否则输出最小的max（碰精队max - 碰精队min，杠精队max - 杠精队min)。

具体思路：

首先对二分图进行染色，然后把每一组的最大值和最小值求出来。再求出整个区间的最大值和最小值。把点权放置在线段上进行处理，每一次二分答案，这个时候合法区间被分成了两组，

然后判断当前两种不能放在一起的能不能分别放置在这两个区间中，注意单点的时候，这个需要特判。

AC代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 # define ll long long
  4 # define inf 0x3f3f3f3f
  5 const int maxn = 2e5+100;
  6 const int  N = 15;
  7 const int mod = 1e9+7;
  8 int n;
  9 int a[maxn];
 10 int color[maxn];
 11 vector<int>Edge[maxn];
 12 int flag;
 13 void  dfs(int u,int type)
 14 {
 15     color[u]=type;
 16     for(int i=0; i<Edge[u].size(); i++)
 17     {
 18         int to=Edge[u][i];
 19         if(color[to]!=0&&color[to]==type)
 20             flag=1;
 21         if(color[to]!=0)
 22             continue;
 23         dfs(to,-type);
 24     }
 25 }
 26 struct node
 27 {
 28     pair<int,int>t1,t2;
 29 } q[maxn];
 30 map<int,int>vis;
 31 int sz[maxn];
 32 int minn=inf,maxx=0;
 33 int id=0;
 34 bool check(int mid)
 35 {
 36     for(int i=1; i<=id; i++)
 37     {
 38         if(sz[i]>=2)
 39         {
 40             if(q[i].t1.second<=minn+mid&&q[i].t2.first>=(maxx-mid))
 41                 continue;
 42             if(q[i].t2.second<=minn+mid&&q[i].t1.first>=(maxx-mid))
 43                 continue;
 44         }
 45         else if(sz[i]==1)
 46         {
 47             if(q[i].t1.first<=minn+mid||q[i].t1.first>=(maxx-mid))
 48                 continue;
 49         }
 50         return false;
 51     }
 52     return true;
 53 }
 54 int main()
 55 {
 56     scanf("%d",&n);
 57     for(int i=1; i<=n; i++)
 58     {
 59         scanf("%d",&a[i]);
 60         minn=min(minn,a[i]);
 61         maxx=max(maxx,a[i]);
 62     }
 63 //    cout<<minn<<" "<<maxx<<endl;
 64     int m,st,ed;
 65     scanf("%d",&m);
 66     for(int i=1; i<=m; i++)
 67     {
 68         scanf("%d %d",&st,&ed);
 69         Edge[st].push_back(ed);
 70         Edge[ed].push_back(st);
 71     }
 72     flag=0;
 73     for(int i=1; i<=n; i++)
 74     {
 75         if(color[i]!=0)
 76             continue;
 77         dfs(i,i);
 78         if(flag)
 79             break;
 80     }
 81     if(flag)
 82         printf("impossible
");
 83     else
 84     {
 85         for(int i=1; i<=n; i++)
 86         {
 87             q[i].t1=make_pair(1e9+1,0);
 88             q[i].t2=make_pair(1e9+1,0);
 89         }
 90         for(int i=1; i<=n; i++)
 91         {
 92             if(!vis[abs(color[i])])
 93                 vis[abs(color[i])]=++id;
 94             sz[vis[abs(color[i])]]++;
 95             if(color[i]>0)
 96             {
 97                 q[vis[abs(color[i])]].t1.first=min(q[vis[abs(color[i])]].t1.first,a[i]);
 98                 q[vis[abs(color[i])]].t1.second=max(q[vis[abs(color[i])]].t1.second,a[i]);
 99             }
100             else
101             {
102                 q[vis[abs(color[i])]].t2.first=min(q[vis[abs(color[i])]].t2.first,a[i]);
103                 q[vis[abs(color[i])]].t2.second=max(q[vis[abs(color[i])]].t2.second,a[i]);
104             }
105         }
106         int l=0,r=maxx-minn;
107         // cout<<l<<" "<<r<<endl;
108         int ans=-1;
109         while(l<=r)
110         {
111             int mid=l+r>>1;
112             if(check(mid))
113             {
114                 ans=mid;
115                 r=mid-1;
116             }
117             else
118                 l=mid+1;
119         }
120         if(ans==-1)
121             printf("impossible
");
122         else
123             printf("%d
",ans);
124     }
125     return 0;
126 }