题解 | #知识竞赛#

个人向题解

思路在注释上

//  https://www.bilibili.com/video/BV1MG411z7Yz/?spm_id_from=333.999.0.0&vd_source=d0319d94edfd26259a11eeed2b2f9fc3

//      贪心
//      题目要求两个人的推理能力之和 与 阅读能力之和
//      以 a-b 的绝对值为依据进行排序

#include <bits/stdc++.h>
using namespace std;

int t,n,m;
void solve()
{
    cin>>n;
    vector<pair<int,int>> a;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        a.push_back({x,y});
    }
    //  按差值绝对值排序
    sort(a.begin(),a.end(),[](const pair<int,int>&a, const pair<int,int>&b){return abs(a.first-a.second) < abs(b.first-b.second);});
    int max1=a[0].first,max2=a[0].second;//差值绝对值 <= 当前这个人的差值绝对值的 那些人的 最大推理能力 以及 最大阅读能力
    int ans=0;
    for(int i=1;i<n;i++)
    {
        if(a[i].first<=a[i].second)//当前这个人推理能力不如阅读能力
        {//那么他和某个人（排他前面的人）的推理能力之和 一定小于 阅读能力之和
            ans=max(ans,a[i].first+max1);
        }
        else {//    当前这个人推理能力更强
        //那么他和某个人（排他前面的人）的推理能力之和 一定大于 阅读能力之和
            ans=max(ans,a[i].second+max2);
        }
        max1=max(max1,a[i].first);//更新前i个人里面的最大推理能力 以及 最大阅读能力
        max2=max(max2,a[i].second);
    }
    printf("%.1f\n",ans/2.0);
}
int main()
{
    solve();
}