【2021】阿里巴巴编程题（4星）第5题

自己想了半天才搞明白，还需要努力

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
const int N = 200010;
struct ab{
    int a,b;
    bool operator<(const ab& T)const{
        return abs(a-b)<abs(T.a-T.b);
    }
}s[N];
float maxMin;
int main() {
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        s[i].a= a;
        s[i].b= b;
    }

    //按照 abs(A_i-B_i)排序，意味着 A_i-B_i
    sort(s,s+n);
    float ans=0.0;
    int amax = s[0].a;
    int bmax = s[0].b;
    for(int j=1;j<n;j++)
    {
        int a = s[j].a;
        int b = s[j].b;
        float cur = 0.0;

        /*
            假设aj<bj 需要一个人来尽可能提升自己的a能力，所以在前面的人员中找amax=max(a),设这个人是k，则有abs(ak-bk) < abs(aj-bj)
            那如何判断(ak+aj)/2 < (bk+bj)/2呢
                当 ak>bk : ak-bk < bj- aj --> ak+aj < bk+bj --> min(A,B) = (ak+aj)/2
                当 ak<bk : 已假设aj<bj，所以 --> ak+aj< bk+bj (小的相加<大的相加) --> min(A,B) = (ak+aj)/2
            综上，当aj<bj时，不管前面找到的最大的a这个人k的另一个能力b如何，到最后取的min都是(ak+aj)/2，所以j的a和b大小（aj和bj的关系）就可以决定最终的答案
            当 aj > bj情况也是一样的，最后的取值也是 (bk+bj)/2
        */
           
        if(a<b)  
            cur = (a+amax)/2;
        else   //当 aj > bj情况也是一样的，最后的取值也是 (bk+bj)/2
        {
            cur = (b+bmax)/2;
        }
        ans = max(ans, cur);
        amax = max(a, amax);
        bmax = max(b,bmax);
    }
    printf("%.1f",ans);

    return 0;
}