阿里笔试 附代码C++ 2020.4.15

第一题
n个人，每个人有一个特征值a，给n个人安排座位，最大化邻座两个人之间的特征值差异程度之和。
输入：
第一行一个正整数n，带表总人数
第二行包含n个正整数，第i个正整数ai表示第i个人的特征值
注意:邻座的定义是第i人(1<i<n)的邻座是i-1,i+1; 第1人的邻座是2,n; 第n人的邻座是1,n-1。邻座i,j差异值是|ai-aj|,取绝对值。每对邻座差异值只算一次。
输出
第一行：最大差异值
第二行：输出用空格隔开的n个数，满足差异值最大化，重新排列过的特征值。（如果有多组，输出一组即可）
题解：
使用了交叉排序的思想，比如对于 3,6,2,9。
第一步：排序，2,3,6,9, 时间复杂度O(nlogn)
第二步：交叉排序，先选最大和最小的出来排列：2,9，这两个数的差异值肯定最大；再选第二大和第二小的数出来，交叉排列，6,2,9,3，3是和9差异第二大的数，6是和2差异第二大的数；如此循环。特殊情况是最后只剩一个数，这种情况，放在头部或者尾部都一样。
第三部：计算排列过后特征值的差异值之和，注意这里用int会溢出（用int只通过了0.3, 笔试结束后看别人题解才发现[捂脸]，还是太菜）。特征值的取值范围是0到10的9次方.

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <limits.h>
#include <string>
#include <queue>
#include <unordered_map>
#include <iomanip>
using namespace std;

int main() {
    //读数据
    int n;
    cin>>n;
    vector vec(n);
    for(int i=0;i<n;i++){
        cin>>vec[i];
    }
    //排序
    sort(vec.begin(),vec.end());
    //交叉排序
    vector nvec(n,0);
    int left=n/2-1;
    int right = left+1;
    int i=0;
    for(i=0;i<=n/2;i++){
        if(left=n) break;
        if(i%2==1){
            nvec[right] = vec[i];
            nvec[left] = vec[n-1-i];
        }
        else{
            nvec[left] = vec[i];
            nvec[right] = vec[n-1-i];
        }
        left--;
        right++;
    }
    //处理特征值为奇数个的特殊情况
    while(i<=n/2){
        if(right<n){
            nvec[right] = vec[i];
            right++;
        }
        else if(left>=0){
            nvec[left] = vec[i];
            left--;
        }
        i++;
    }
    //求最大差异值之和
    long count = 0;//注意这里用long，用int会溢出
    for(int i=1;i<n;i++){
        count += abs(nvec[i]-nvec[i-1]);
    }
    //输出两行结果
    count += abs(nvec[0]-nvec[n-1]);
    cout<<count<<endl;
    for(int i=0;i<n;i++){
        cout<<nvec[i]<<" ";
    }
    cout<<endl;
    return 0;
}

第二题
n个员工，每个员工都有个推理能力值Ai和阅读能力值Bi。要选两个员工i和j去竞赛，他们的平均推理能力是x=(Ai+Aj)/2, 平均推理能力是y=(Bi+Bj)/2。目标是从n个员工中选择两个人，使得min(x,y)尽可能大。请问最大值是多少。
输入：
第一行：正整数n
后面n行对应第i位员工的Ai和Bi。
输出：
一行一个一位小数表示最大值

只想到了暴力解法，O(n2)，通过了0.3，请问有老哥想到优美解法吗？

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <limits.h>
#include <string>
#include <queue>
#include <unordered_map>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> b(n);

    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }

    double maxxy = -1.0;

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){ 
            double x=(a[i]+a[j])/2;
            double y=(b[i]+b[j])/2;
            maxxy = max(min(x,y), maxxy);
        }
    } 

    cout<<fixed<<setprecision(1)<<maxxy<<endl;

    return 0;
}