阿里飞猪1028秋招笔试真题解析

前言

题目难度适中，有些许灵活。 第一题模拟题，偏打卡。 第二题需要一些灵活的处理，比较好思维。 第三题也是偏向思维的题目，有一定难度。

T1

小红来到了一家饭馆，该饭馆一共有n道菜，第i道菜的价格为ai。其中有一些菜里有蘑菇。

小红希望点k道菜，总价格越小越好。由于小红不喜欢吃蘑菇，她希望点的菜最多有m道菜中包含磨菇。小红想知道最终最小的总价格是多少。

输入描述

第一行输人三个正整数n,m,k，空格隔开。

第二行输入一个01串，第i个字符是0代表该菜不包含蘑菇，是1代表包含蘑菇。

第三行输入n个正整数，第i个数代表a[i]

1≤m≤k≤n< 10^5

1≤a[i]≤10^9

输出描述

一行，代表最小总价格。如果选不出来输出-1.

输入
3 1 2
001
10 20 30
输出
30

输入
3 1 2
111
10 20 30
输出
-1

思路与代码

按照菜价排序后，模拟题意选菜即可。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(vector<int> a, const vector<int> b) {
  return a[0] < b[0];
}
int n, m, k;
long long ans;
string s;
int main() {
    cin >> n >> m >> k;
    vector<vector<int>> nums(n, vector<int>(2));
    cin >> s;
    for (int i = 0; i < n; i++) {
        nums[i][1] = s[i] - '0';
    }
    for (int i = 0; i < n; i++) cin >> nums[i][0];
    sort(nums.begin(), nums.end(), cmp);
    for (int i = 0; i < n; i++) {
        if (k <= 0) break;
        if (nums[i][1] == 1) {
            if (m > 0) {
                ans += nums[i][0]; m--; k--;
            }
            continue;
        }
        k--;
        ans += nums[i][0];
    }
    if (k > 0) {
        cout << -1 << endl;
    } else {
      cout << ans << endl;
  }
    return 0;
}

T2

小红拿到了一个仅由小写字母组成的字符串s,她希望你构造一个字符串t，满足以下条件：

1.也是仅由小写字母组成，长度和s相同。

2.t是回文串。

3.的字典序小于s，且在满足以上条件时字典序尽可能大。

输入描述：

一个字符串s,字符串长度不超过100000。

输出描述：

如果无解，则输出-1。否则输出一个字符串t。

输入
abc
输出
aba
输入
cba
输出
cac

思路与代码

根据题意，先去除len(s)/2个字符，用他来构造回文串t，看t和s的大小关系，如果不满足则在前len(s)/2字符内贪心的找到最后一个不为'a'的字符（假设位置idx），将它的字符值-1，并且让(idx,len(s)/2]位置的值都置为z即可。

对于s中字符全为a的情况，输出-1.

#include<iostream>
#include<vector>
#include<string>
using namespace std;

string s, t;
int main()
{
  cin>>s;
  for(int i = 0; i<=(s.size()-1)/2; i++) {
    t += s[i];
  }
  int up = (s.size()-1)/2;
  if(s.size()%2 == 1) up--;
  for(int i = up; i>=0; i--) t += s[i];
  if(t>=s) {
    int idx = (s.size()-1)/2;
    while(idx >= 0 && s[idx] == 'a') {
      t[idx] = 'z';
      idx--;
    }
    if(idx < 0) t = "-1";
    else {
      t[idx]--;
      for(int i = (s.size()-1)/2+1; i<s.size(); i++) {
        t[i] = t[s.size()-i-1];
      }  
    }
    
  }
  cout << t << endl;
  return 0;
}

T3

小红希望你构造一棵树，满足共有n个节点，且恰好有k个节点的度数为3。你能帮帮她吗？

输入描述：

输入两个整数n,k，用空格隔开。

1≤k≤n≤10^5

输出描述：

如果无解，请输出1。否则输出n-1行，每行输出两个正整数u,v,用空格隔开，代表节点u和节点v连一条边。

请务必保正最终构造的为一棵树，且恰好有k个节点的度数为3。有解时输出任意即可。

1≤u,v≤n

输入
4 1
输出
1 2
1 3
1 4
输入
4 2
输出
-1

思路与代码

从根节点开始构造，发现只要构造出一棵“根节点有三个孩子，其他所有非叶子节点都有两个孩子”的树即可。所以按照这个思路构造k个节点，剩下的节点成一条链状，接在最后一个节点上即可。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> vv[100005];
int n,k;
int main()
{
  cin>>n>>k;
  int cur = 1, mx = 2;
  bool ok = true;
  for(int i = 1; i<=k; i++) {
    if(mx+1 > n) {
      ok = false;break;
    }
    int num = 2;
    if(i == 1) num = 3;
    for(int j = 0; j<num; j++) vv[cur].push_back(mx++);
    cur++;
  }
  while(mx <= n) {
    vv[mx-1].push_back(mx);
    mx++;
  } 
  if(ok == false) cout << -1 << endl;
  else {
    for(int i = 1; i<=n; i++) {
      for(auto x : vv[i]) {
        cout << i << " " <<x <<endl; 
      }
    }  
  }  
  return 0;
 }