巧妙逻辑归纳题

题意简述：

n个(A,B)，找出两个人，使得 X=(B1+B2)/2, Y=(A1+A2)/2，求min(X,Y)的最大值

注意：这里让X=(A1+A2)/2, Y=(B1+B2)/2时，结果不变，利于顺序理解。

逻辑树分析：

我们需要选择两个人，记为i和j，先选i再选j，则所有情况的逻辑树如下：

大家自己手画一遍就理解了：

当 Ai + Aj < Bi + Bj时，X < Y，结果就是X值；

当 Ai + Aj > Bi + Bj时，X > Y，结果就是Y值；

核心排序操作

为了让 X 与 Y 的大小关系只与 j 的值有关，我们直接按照abs(A-B)从小到大的顺序对n个人排序：

这样，在先选定 i 时，由于后面的 j 的abs(A-B)一定大于（或等于） i 的abs(A-B)；

所以，当Ai < Bi时，若Aj < Bj，则 X < Y，若Aj > Bj，则 X > Y；

当Ai > Bi时，若Aj < Bj，则 X < Y，若Aj > Bj，则 X > Y；

即，最终到底是 X 更小还是 Y 更小，只与 j 的 A 值更小还是 B 值更小有关。

PS: 我们就把逻辑树中的全部情况归纳成红色路径的情况了。

结果：

因为若 j 的 A 值更小，最终结果就是 X ，那么在选定 j 时只需要找前面 A 值最大的 i， 即可实现：ans = X = (Ai + Aj)/2 最大；

同样的，若 j 的 B 值更小，最终结果就是Y，那么在选定 j 时只需要找前面 B 值最大的 i，即可实现：ans = Y = (Bi + Bj)/2 最大。

C++代码实现

我们通过按照 A-B 的绝对值从小到大排序后，只需要遍历一遍 j 并同时记录前面所有人的 A 最大值和 B 最大值就好了。

代码如下：

#include<vector>
#include<algorithm>
using namespace std;

bool abs_cmp(const pair<int, int>&n1, const pair<int, int>&n2) {
    return abs(n1.first - n1.second) < abs(n2.first - n2.second);
}

double No5_guiNa(vector<pair<int, int>>&val) {
    int n = val.size();
    sort(val.begin(), val.end(), abs_cmp);
    int maxX = val[0].first, maxY = val[0].second;
    double ans(0.);
    for (int i = 1; i < n; i++) {    // 这里的 i 就是后手选的 j，从第二个人开始遍历
        int cur;
        if (val[i].first > val[i].second)   // A > B, X > Y
            cur = val[i].second + maxY;
        else cur = val[i].first + maxX;
        if (cur > ans)ans = cur;
        maxX = max(val[i].first, maxX);
        maxY = max(val[i].second, maxY);
    }
    return ans / 2;
}

int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> val(n);
    for(int i=0;i<n;i++){
        cin>>val[i].first>>val[i].second;
    }
    cout<< No5_guiNa(val)<<'\n';
    return 0;
}