11：30，过题。12：50，忘记做法。
吃饭时不该看未来日记的，Ynoj 害人不浅（确信）。
以上为个人吐槽。
题目大意
不知道题目翻译是个啥。。。但讨论区有大佬给出了精确的翻译。我改得符合题目背景一点放上来：
每一个羊有一个区间 \(l_i,r_i\) ，如果两只羊区间相交，我们称为两只羊“捆在一起”
现在，你需要重新排列 \(n\) 只羊，使“捆在一起”的羊之间的最大距离最小，输出方案
距离定义为两只羊中间的羊的数量（其实无所谓了，毕竟只要输出方案）
提示：注意一只羊可以和多只羊捆在一起。
做法
二分加贪心。
二分答案，问题变成了保证两个相交的羊之间距离不超过二分的答案 mid 。
不妨从小到大选择这个位置应该放哪一只羊，那么我们可以维护出一个数组 fin ,表示每只羊当前最远能放到的位置是哪里。
首先判断无解情况。设当前选择到了序列的位置 i ，我们统计出数组 finc，finc[j] 表示 fin 数组值在从 i 到 j 的羊的个数
显然，无解的情况就是 \(finc[j] > j-i+1\) 。证明：根据 fin 的定义，每次选择后，限制变多，fin 不会变大。如果大于，就不能将 fin 在 i~j 之间的羊塞进 \(j-i+1\) 个位置中。
然后我们考虑这个位置放哪只羊。根据无解情况，我们发现了一个限制：如果 \(finc[j]=j-i\) ，那么我们放的羊肯定要小于等于 j 。不然放下一只羊时必定会导致无解情况（ finc可能会增加，\(j-i\) 必定会减小）。而我们只需要满足 j 最小的限制就行了。原因是满足了以后之后的 finc 都会减一，避免了上面的情况。
满足上面的限制后，我们贪心地选取 r 最小的羊。因为我们要尽量避免相交，如果一开始就选取大的 r ,之后的相交数只会吧变多不会变少。
最后一个步骤，选择完点后，我们要根据这个点更新之后羊的 fin 。具体地，我们要保证与之相交的点最远放到的位置小于等于 \(i+mid\) 。
也许我讲的不够清楚，我再把 check 的总过程放上来：
inline bool check(int mid)
{
for(int i = 1;i <= n;i ++) fin[i] = n, ans[i] = 0, fl[i] = 0;
for(int i = 1;i <= n;i ++)
{
int b = 0, p = 0;
memset(finc, 0, sizeof(finc));
for(int j = 1;j <= n;j ++) if(!fl[j]) finc[fin[j]] ++;//统计 fin 为 j 的羊的只数
for(int j = 1;j <= n;j ++) finc[j] += finc[j - 1]; //实际上 finc 就是求一遍前缀和
for(int j = i;j <= n;j ++) if(finc[j] > j - i + 1) return 0;//判无解（被标记的点统计 finc 时就没有贡献，无需额外判断）
for(int j = n;j >= i;j --) if(finc[j] == j - i + 1) b = j;//寻找最小的限制
for(int j = 1;j <= n;j ++) if(!fl[j] && fin[j] <= b && r[j] < r[p]) p = j;//在限制内寻找最小的 r
fl[ans[i] = p] = 1;//标记，之后不能再选
for(int j = 1;j <= n;j ++) if(l[j] <= r[p] && l[p] <= r[j]) fin[j] = min(fin[j], i + mid);//更新fin
}
return 1;
}
为了方便判断，我在主函数中将 \(r[0] = INF\)。需要注意一下
后记
其实，我们判断无解时用了一个叫做霍尔定理的东西。但由于太过显然，我就直接证了一遍。有兴趣的同学可以自行了解。
标签：int,题解,mid,相交,CF309E,finc,fin,我们 From： https://www.cnblogs.com/closureshop/p/16800293.html