华为 8.31 机试第三题

#include <bits/stdc++.h>

using namespace std;

int maxDis = 1000;
int main()
{
    int D;
    int N;
    cin >> D >> N;
    vector<int> distance(N + 2);
    vector<int> weight(N + 2);
    distance[0] = 0;
    distance[N + 1] = D;
    weight[0] = 0;
    weight[N + 1] = 0;
    //标识在第i个加油站的时候花费的最小时间代价
    vector<int> dp(N + 2, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> distance[i];
        cin >> weight[i];
        if (distance[i] - distance[i - 1] > maxDis)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    if (D <= maxDis)
    {
        cout << D / 100 << endl;
        return 0;
    }
    else
    {
        for (int i = 1; i <= N + 1; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (distance[i] - distance[j] > maxDis)
                    break;
                int add = 0;
                if (i != N + 1)
                    add = 1;
                dp[i] = min(dp[i], dp[j] + weight[i] + (distance[i] - distance[j]) / 100 + add);
            }
        }
    }
    cout << dp[N + 1] << endl;
    return 0;
}


华为第三题 只ac12%,哪位大佬帮忙看看有啥问题#华为机试#
全部评论
dp复杂度O(n^2),可以参考力扣871解法二改成贪心+小顶堆,复杂度O(nlogn)
3 回复 分享
发布于 2022-09-01 16:53 湖北
跟我的一毛一样,就是用dp数组存所有时间了,这样没有考虑到中间站点不是100的整数倍,会有偏差。正确AC的代码应该是只用DP数组存到达每个站点充电和等待的时间,然后最后从 能到达终点的站点 中选择最小的那个,再加上终点距离除以100
3 回复 分享
发布于 2022-09-01 15:47 辽宁
一楼说的很对。。计算dp时不要算上 距离/速度的时间,会有非整除误差。 dp数组只需要存储花费在“停车+加油”的时间
2 回复 分享
发布于 2022-09-01 15:51 北京
楼主什么方向,为啥我没收到笔试通知,简历挂了嘛😂
1 回复 分享
发布于 2022-09-01 15:41 北京
老哥,能描述下第三题题目吗?实在搜索不到啊
点赞 回复 分享
发布于 2022-09-01 19:06 广东
感谢各位大佬,懂了
点赞 回复 分享
发布于 2022-09-01 16:25 北京
要用double 输出结果再转成int 我过了78%
点赞 回复 分享
发布于 2022-09-01 15:55 浙江
数据未全部读取
点赞 回复 分享
发布于 2022-09-01 15:42 江苏
上二叉树
点赞 回复 分享
发布于 2022-09-01 15:15 浙江

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
1
19
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务