9.4 美团2024届秋招笔试第一场_小美的排列构造

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网 (nowcoder.com)

4.小美的排列询问

小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？

排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。

输入描述：

输出描述：

思路：利用每个元素只出现一次，每个元素能“记住”自己“附近”的元素则很简单能完成。用哈希表来保存，key为自己，val为前一个元素；

代码实现：

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main() {
    int n,pre=0;
    //每个元素只出现一次
    cin>>n;
    //key为保存的元素，val为该元素的上一个元素,无上一个则为0
    unordered_map<int,int> m;
    for(int i=0;i<n;i++)
    {
        int a=0;
        cin>>a;
        m[a]=pre;
        pre=a;
    }
    int x,y;
    cin>>x>>y;
    if(m[x]==y||m[y]==x)
    {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
 
}

5.小美的排列构造

小美定义一个数组a的权值计算如下：

首先将a的每一对相邻两项求和，得到一个b数组。那么b数组的最大值减最小值即为a数组的权值。

例如，若a=[2,1,3]，那么b=[3,4]，b数组的极差是1。因此a数组的权值为1。

现在小美希望你能构造一个长度为n的排列，满足权值尽可能小。你能帮帮她吗？

排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。

 输入描述：

输出描述:

思路：b数组元素=a数组元素相邻数的和，要让b数组的最大值-最小值最小，则只要让a数组中小大小大。。。这样元素排列。

代码实现：

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n=0;
    cin>>n;
    int low=1,high=n;
    vector<int> v;
    while(low<=high)
    {
        if(low==high) 
        {
            v.push_back(low);
            break;
        }
        v.push_back(low);
        v.push_back(high);
        low++;
        high--;
    }
    for(auto e:v)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    return 0;
}