美团2021校招笔试-编程题题解

原创

用户9667323

发布于 2022-04-27 00:26:29

6450

文章被收录于专栏：基础算法基础算法

题目链接

小美的送花线路

题意：

有n个点的一棵树，玩家开始在1号点，要遍历所有的点，使得走过的路程最短。

问：每个点到1号点的距离和是多少？玩家遍历的最短路程是多少？

题解：
由于玩家行走的路径是有来有回，因此需要简化问题，将行走分为两部分，以c号点为界。可以得到一个结论：去往其他三个方向后都得回来，只有某一个方向是可以一去不返。
那么我们可以操控的空间就是：令一去不返这个方向距离 1号点最远。也就是找出距离1号点最远的点u，转化为树上的遍历问题。
image.png
穿插知识点：树的直径。定义：一棵树的直径就是这棵树上存在的最长路径（也就是距离最远的两个点相连的路径）。

找出直径：也就是寻找两个最远的点：(u, v)。从任意点 x 出发，距离 x 最远的点 u，即是直径的一个端点（找最远点使用遍历或者最短路知识皆可）。再从 u 出发，寻找距离 u 最远的点 v 即是另一个端点。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <queue>
using namespace std;

#define N 60010

struct Edge {
    int from, to, dis, nex;
}edge[N << 1];
int head[N], edgenum;

void addedge(int u, int v, int w) {
    Edge E = { u, v, w, head[u] };
    edge[edgenum] = E;
    head[u] = edgenum++;
}

///////
int maxdep = 0, deptotal = 0;

void dfs(int u, int father, int depth) {
    maxdep = max(maxdep, depth);
    deptotal += depth;

    for (int i = head[u]; ~i; i = edge[i].nex) {
        int v = edge[i].to;

        if (v == father)
            continue;

        dfs(v, u, depth + edge[i].dis);
    }
}

int main() {
    memset(head, -1, sizeof(head)); edgenum = 0;

    int n, alldis = 0;
    
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);

        alldis += w;
    }

    dfs(1, -1, 0);

    printf("%d %d\n", deptotal, alldis * 2 - maxdep);

    return 0;
}

小美的评分计算器

题意：

给出5个整数,a,b,c,d,e。问(a+2b+3c+4d+5e) / (a+b+c+d+e) 的结果，要求保留1位小数，无需进位（即2.89输出2.8）。

小技巧：如果直接使用c++的print等方式会四舍五入。我们可以将答案减去0.5，再四舍五入达到此效果。

#include<stdio.h>
using namespace std;

int main() {
    double ans = 0, count = 0;

    for (int i = 1, v; i <= 5; i++)
    {
        scanf("%d", &v);
        ans += v * i;
        count += v;
    }

    printf("%.1lf\n", ans / count - 0.05);

    return 0;
}

小美的外卖节省钱计划

是个阅读理解题。这里不再赘述。

#include<stdio.h>
#include<algorithm>
using namespace std;

int main() {
    int n, u, v, ans1 = 0, ans2 = 0;

    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &u, &v);
        if (u > v)
        {
            ans1 += u;
            ans2 += u - v;
        }
        else
        {
            ans1 += max(u, v);
        }
    }

    printf("%d %d\n", ans1, ans2);

    return 0;
}

小美的代金券要过期啦

题意：

1 1 1 1 1

两个相邻且相同数字可以合并+1放回原位。比如把 1 1 9-> 2 9。

问最多可以操作多少次。数字个数500个，数字为1,100的整数。

题解由于此题不存在多项式的解，后续会分析其原因，但即使当成模拟题来做，也可以使用动态规划作为思考开端。
- 穿插知识点：动态规划的无后效性

为了满足最优子问题，我们思考时应避免问题的后效性。后效性举个例子：问题：1 1 2 3 1 1 2
有后效性的合并是 2 2 3 1 1 2 -> 3 3 1 1 2。无后效性的合并是2 2 3 2 2 -> 3 3 3。区别：有后效性在做了一次合并后，依然存在最小数字 1 未合并的问题。不便提出一个子问题。无后效性在做了一次合并后，最小数字 1 已完全合并。这样的好处是：我们可以提出子问题为：合并当前最小的数字。不断处理这个子问题，至多100次就可以终结。

考虑合并当前最小的数字的问题，假设刚开始最小数字为1，分类讨论(因为1是最小的，所以下面举例中的？是比1大的任意数字)：
局部只有一个连续的1，那么无法进行合并。如：? 1 ?，而且因为1是当前最小的，这个1后续也无法再合并，一直残留着。
局部有偶数个1，直接进行合并即可。? 1 1 1 1 ? -> ? 2 2 ?。
局部有5,7,9,···等奇数个1，把1残留到中间，其他合并。? 1 1 1 1 1? -> ? 2 1 2 ?，因为本次操作后，两边的2还有合并的机会。若不这么做，结果是 ? 2 2 1 ?，那么右边的1也没有合并的机会了。
局部有3个1，如 ? 1 1 1 ?。无论哪种合并方式，都无法确切判断是否最优的，也就是出现了两个不可预料的分支。极端一点：111 ? 111···，100个数字里最多有25段111，也就是 2^25 种组合来推导下一个子问题。这个解空间已经非常庞大了。
根据上述思路，每次遍历处理当前最小数字合并的子问题，除了4，123均是有明确合并手段的。由于没有明确的最优解，这里不再贴模拟的解法代码。

引用

上文一些素材来源于以下几位博主，向知识分享的朋友致谢。

树的直径定义

1题题解图片

关于我们

欢迎关注公众号《奇迹狗狗》，很开心在这里能和你相遇~

我们会分享一些技术文章，包括但不限于游戏技术、云原生、ACM题解、基础编程知识等，如果能授人以渔，荣幸之至！

我们也会做一些有温度的产品、游戏和脱单小群，会陆续分享给大家，如果能博君一笑，再好不过！

产品列表：

★ WorkerHub小程序，信息均来自各个大厂员工爆料，可以查询各个公司/部门/岗位的工作做细、工作体验、工作评价等，供打工er找工作的时候参考，避雷卷王团队/天坑团队！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

登录后参与评论

0 条评论

热度