P7339 Kotori-分治与排序

· · 题解

题目链接

P7339 跳转

题意简介

给定2^k个数，每次两两分组比较大小，更大的数晋级下一轮。

给定一个整数m，对于每次比大小都可以给任意双方加上m从而改变可能的结果。

需要判断第一个元素是否有可能是最终胜者。

题目分析 O(nlog^2n)

首先考虑贪心，但是贪心思路并不明显。

注意到比大小的结构类似淘汰赛，是一颗满二叉树，因此每个子树都是和原树相同的结构和问题，满足最优子结构。

所以考虑分治，分，解，合。

具体地，对于每个子问题，需要求所有可能获胜元素的集合。

那么对于分出的最小单位即一个元素，这个集合包含且只包含它自己一个元素，直接返回，这就是递归边界。

确定边界后，考虑普遍情况。对于某一非叶子节点，左子树有一可能获胜元素的集合，右子树也有一可能获胜元素的集合。

找出集合中的最小元素，与对手集合中的每一个元素作差，如果大于m，则对手集合中的这个元素无法获胜。因为这意味着这个元素即使加上m也无法大于等于对手集合最小的元素，无论如何都是输，只能被淘汰。

即对于任意一个该层胜者元素x，均有x > y+m，其中y为另一侧集合最小元素。

对于如何快速地找出最小值并找到可以获胜的元素，比较容易想到进行排序找出最小值后，使用二分查找找到对手集合第一个大于这个最小值的元素，此时该元素以右的所有元素均可以获胜。

再将这些获胜的元素放入一个集合中返回，等待下一层对战，同时维护集合单调保证二分可用。

最终只需判定首元素是否存在于根节点可行夺冠集合中即可。

:::success[关键代码]

vector<int> MergeSort(int l,int r,int dpt){
    vector<int> sel,ser,se;//可能赢的人
    se.push_back(a[l]);
    if(l == r) return se;
    se.erase(se.begin());
    int mid = (l+r) >> 1;
    //分
    sel = MergeSort(l,mid,dpt+1);
    ser = MergeSort(mid+1,r,dpt+1);
    //合
    //合并左集合和右集合，把一定输的踢出去
    //左边有可能赢的
    auto p = lower_bound(ser.begin(), ser.end(), sel[0]-m);
    for(auto i=p;i!=ser.end();i++){
        se.push_back(*i);
    }
    p = lower_bound(sel.begin(), sel.end(), ser[0]-m);
    for(auto i=p;i!=sel.end();i++){
        se.push_back(*i);
    }
    sort(se.begin(), se.end());
    return se;//返回有序vct
}

:::

此外，对于在有序容器中判断某数是否存在，可以使用以下函数：

bool search(int x){
    auto it = lower_bound(se.begin(), se.end(), x);//保证大于等于x
    return it!=se.end() && !(x < *it);//判断是否没有大于等于x的数以及这个数是否小于x
}