美团2021校招笔试真题

1、小美的送花线路

【题目描述】
小美是美团的一名鲜花快递员，鲜花是一种保质期非常短的商品，所以需要尽快送到客户手中，公司对于骑手的一个要求就是要规划送花的线路，使得骑手送完所有订单走的路程尽可能少。(骑手开始派送时带走了所有需要派送的花，不必每单后返回花店，路程结算是从花店出发，到送完最后一名客户为止，不计算从最后一名客户家回到花店的时间)
公司对于骑手的绩效评价是取决于两个指标，一是从花店到所有客户地址的距离之和，另一个是骑手实际走的路程。
设花店始终位于1号位置，客户共有n-1个，其编号为2~n。令dis(i,j)表示i号位置到j号位置的距离，即分别计算∑_(i=2)^n▒〖dis(1,i)〗,和骑手实际所走的最短路程。
为了简化问题，我们约束这n个位置构成的是一棵树，即只有n-1条边在其中互相连接，且保证n个点彼此连通。
输入描述：
输出第一行包含一个正整数n，即花店和客户的总数。(1≤n≤30000)
接下来有n-1行，每行有三个整数u,v,w，表示在u和v之间存在一条距离为w的道路。(1≤w≤1000)
输出描述：
输出包含两个整数，中间用空格隔开，分别表示花店到所有客户地址的距离之和和骑手实际走的路程。
输入样例：
5
1 2 3
1 3 1
1 4 2
2 5 1
输出样例：
10 10

【解题思路】
BFS，利用map存储该节点的所有子节点的编号以及该节点到下一节点的权值，在queue中push入队时，不断更新根节点到下一节点的总代价，也就是distant(1, i)，当该节点没有子节点时说明到了叶子节点处，更新最长的路径长度，最后用所有的weight的和减去该最长路径（只走一次）就是骑手走的总距离。

【参考代码】
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    unordered_map<int, vector<pair<int, int>>> mp;
    int total = 0;
    while (--n) {
        int sor, des, w;
        scanf("%d%d%d", &sor, &des, &w);
        mp[sor].push_back({des, w});
        total += w;
    }
    queue<pair<int, int>> q;
    q.push({1, 0});
    int maxLength = -1, sumLength = 0;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        int len = mp[p.first].size();
        if (!len) {
            //total += p.second;
            maxLength = max(maxLength, p.second);
        } else {
            for (int i = 0; i < len; ++i) {
                pair<int, int> tmp = mp[p.first][i];
                q.push({tmp.first, p.second + tmp.second});
                sumLength += (p.second + tmp.second);
            }
        }

    }
    total = total * 2 - maxLength;
    cout << sumLength << ' ' << total << endl;

    return 0;
}

2、小美的用户名

【题目描述】 小美是美团的前端工程师，为了防止系统被恶意攻击，小美必须要在用户输入用户名之前做一个合法性检查，一个合法的用户名必须满足以下几个要求： 用户名的首字符必须是大写或者小写字母。 用户名只能包含大小写字母，数字。 用户名需要包含至少一个字母和一个数字。 如果用户名合法，请输出“Accept”，反之输出“Wrong”。 输入描述： 输入第一行包含一个正整数T，表示需要检验的用户名数量。(1≤T≤100) 接下来有T行，每行一个不超过20的字符串s，表示输入的用户名。 输出描述： 对于每一个输入的用户名s，请输出一行，即按题目要求输出一个字符串。 输入样