CF538H
有 T 名学生，你要从中选出至少 t 人，并将选出的人分成两组，可以有某一组是空的。
有 n 名老师，每名老师要被分配到两个小组之一
对于第 i 名老师，要求所在的小组中的学生人数 ∈[li,ri]。
此外，有 m 对老师不能在同一个小组中。
你需要判断能否满足所有要求，如果可以，请给出一种方案。
t ≤ T ≤1e9，n,m ≤ 1e5。
====================================================================
可以先思考出两个小组的人数，再判定每个老师去哪个小组
先求出 min_r 和 max_l，先不管 t 和 T，如果两个小组的人数分别是 min_r,max_l，那么显然所有老师都能找到小组。然后再来讨论总人数
设第一组人数 n1 = min_r 第二组 n2 = max_l
一、n1 + n2 < t，这个时候肯定要让一个小组人数变多才能满足要求，而这时，n1 是不能变多的，因为 n1 是原来的 min_r。所以 n2 变多更优，那么就让 n2 = t – n1。
二、t <= n1 +n2 <= T，这个时候每个老师都能找到小组，善莫大焉
三、n1 +n2 > T，那么这个时候肯定要减少一个小组的人数了。那么哪个小组可以被减少呢？当然就是 n1 了（与第一种情况同理），所以此时让 n1 = T – n2
现在，我们就有了两个小组的人数了，之后就把老师读入进来然后二分图染色判定一下即可
染色时一定要注意顺序
如果当前老师只能选一个小组，那就染；如果两个都能选，那就让他最后染，因为有可能需要他给其他老师让出位置；那如果两个小组都不能选呢？你觉得呢？
code
if(max_l + min_r < t) n1 = min_r,n2 = t - n1;
else if(max_l + min_r <= T) n1 = min_r,n2 = max_l;
else if(max_l + min_r > T) n1 = max_l,n2 = T - n1;
if(n1 < 0 || n2 < 0)
{
puts("IMPOSSIBLE");
return 0;
}//把人数算出来
//下面是染色
for(int i = 1;i <= n;i ++)
{
if(l[i] <= n1 && n1 <= r[i] && !(l[i] <= n2 && n2 <= r[i])) dfs(i,1);
else if(!(l[i] <= n1 && n1 <= r[i]) && l[i] <= n2 && n2 <= r[i]) dfs(i,2);
else if(!(l[i] <= n1 && n1 <= r[i]) && !(l[i] <= n2 && n2 <= r[i]))
{
puts("IMPOSSIBLE");
return 0;
}
}
for(int i = 1;i <= n;i ++)
if(!v[i])
dfs(i,1);
//你不会还想知道怎么染吧
void dfs(int x,int col)
{
v[x] = col;
for(int i = head[x];i;i = nxt[i])
{
int y = to[i];
if(!v[y]) dfs(y,3 - col);
else if(v[y] == v[x])
{
puts("IMPOSSIBLE");
exit(0);
}
}
}
//完结撒花qwq