美团8.6笔试思路-后端岗

1. 礼盒包装

   给定a、b两种点心的数量，每个礼盒放3个点心，a、b至少各有一个，求最多能包多少个礼盒

• 设2a1b礼盒有x个，2b1a礼盒有y个，线性规划问题：
  max (x+y) s.t. (2x+y ≤ a) && (x+2y ≤ b) && (x ≥ 0) && (y ≥ 0)
• 根据 a b 关系，z = x+y = a或b或(a+b)/3

2. 分割点k实验

   给定一组0，-1，+1数组，分割点k左大于等于0、右侧小于等于0的为异常数据，求最乐观情况下有多少个异常数据

• 记录正数和负数的总数量pos neg
• 遍历数组，记录当前位置左侧的负数数量curneg，更新ans = min(ans, curneg + (pos - curpos))

3. 反转魔法石

   给定一组魔法石正面和反面表示的数字，只有当至少一半相同数字的面朝上可以触发法阵，初始状态为全部朝上，求最少需要翻转多少块石头可以触发法阵，无解输出-1

• 根据初始状态朝上数字出现次数从大到小尝试翻转，如果可以触发则输出次数
• 如果初始正面数字无法触发，则输出反面数字出现次数超过(n+1)/2的最小次数，如果没有则输出-1

至过了91%，可能哪里没有考虑全。测试用例比较弱，只考虑初始正面有超过一半的数字就输出0，否则输出-1就能过73%。

4. 数据拆分

   给定n个样本的类别编号，输入的次序为样本编号，每类样本编号最小的(m+1)/2为训练集，剩下的为测试集。按照样本编号升序输出所有训练集样本及训练集样本

• vector<vector<int> > ybz(k+1); //样本组：ybz[i]保存样本类别i的所有样本</int>
• 根据ybz[i].size()拆分训练集和测试集
• 对总测试集和总训练集排序，然后输出即可

5. 字符串第k位

   将字符串s丢入机器后则输出新字符串s+reverse(s)+"wow"。初始字符串为"MeiTuan"，不停的反复将新字符串丢入机器，求得到的无限长字符串的第k位字母（1 ≤ k ≤ 1e18）

• 用long long数组保存每次丢入机器得到是字符串长度，分别为7 17 37 ...

• 根据k的大小，找到k所属字符串是第几次丢入机器得到的字符串

• 根据k与当前字符串长度的关系，判断该字母是上一字符串的第几个字母，直到k ≤ 7，输出字母即可

  #include<iostream>
  #include<vector>
  #include<string>
  using namespace std;
  int main() {
    int T;
    cin >> T;
  
    string bases("MeiTuan");
    string wows("wow");
    vector<long long> lens = {7};
  
    while(true){
        if(lens.back() > 1e18)
            break;
        auto thislen = lens.back() * 2 + 3;
        lens.push_back(thislen);
    }   
  
    while(T--) {
        long long k;
        cin >> k;
  
        int idx;
        for(idx = 0; idx<lens.size(); ++idx) {
            if(k <= lens[idx])
                continue;
        }
        idx -= 1;
  
        while(k > 7) {
            auto curlen = lens[idx];
  
            // 属于“wow”部分
            if(k > lens[idx-1] * 2) {
                cout << wows[k-lens[idx-1]*2-1] << endl;
                break;       
            }
  
            // 属于上一字符串逆序部分
            if(k > lens[idx-1]){
                k = lens[idx-1] * 2 - k + 1;
            }
            // 遍历上一字符串
            idx--;
        }
  
        // 已经输出过了
        if(k > 7)
            continue;
        // 输出“MeiTuan”的第k位字母
        cout << bases[k-1] << endl;
    }
    return 0;
  }