二分？

紫薯布丁 · 2019-10-20 20:43:28 · 个人记录

二分答案一般用于求最大值最小和最小值最大的问题。

T1 疫情控制

给定一个含n个节点的树，和m个点在树上的位置，要求移动这些点封杀所有子树的最短距离，m个点可同时移动。

m个点可同时移动，问题就转化为求m个点中移动的点最大距离的最小值。这就可以用二分解决这道题目

离根节点越近的节点，控制的节点更多。所以由贪心的思想，所有的军队都要尽可能地往根节点走。

如果当前军队可以到达根节点，那么记录一下它的编号和它到达根节点后还可以走的时间rest。如果这个军队i在根节点的子树x中，那么记录一下子树x的符合这个条件的点中，到根节点后剩余路程最短的点。

如果不可以到达，记录它被”提“到的节点被军队设置了检查点。

将我们已经记录好了的可以到根节点的军队按照剩余路程从大到小排序。

将未被“封死”的子树按照到子树到根节点的距离从大到小排序。

然后依次处理未被“封死”的子树要由哪支军队来管辖。

代码太长，不贴了，早晚这道题重做一遍

T2：

给定 n ** m 的矩阵，从矩阵中取出n个不同行不同列的数字，求n个数中第k大的数字的最小值。

仍然是最大的数字最小的问题，二分答案。

我们二分答案mid，在矩阵中跑行列的二分图匹配，匹配前提是格子中的数字小于等于mid

inline bool dfs(int x,int mid){
    for(int i=1;i<=m;i++){
       if(a[x][i]<=mid){
        if(!b[i]){
            b[i]=1;
            if(!girl[i]||dfs(girl[i],mid)){
              girl[i]=x;return 1;
          }
        }
      }
    }
    return 0;
}

如果有a个比mid小的数能被匹配到，那么也一定会有a-1个数能被匹配到。也就是说，其具有单调性

inline bool pan(int mid){
    memset(girl,0,sizeof(girl));
    int ou=0;
    for(int i=1;i<=n;i++){
        memset(b,0,sizeof(b));
        ou+=dfs(i,mid);
    }
    return ou>=n-k+1;
}

我们求的是第k大的数字最小，那么就会有n-（k-1）个数字比k小，所以我们二分出的答案应满足匹配树x>=n-(k-1)个