4.27华为机试(求大佬交流一下)

1.买水果的最佳方案

题目描述:1-n小时内,有m家水果店会在不同的时间段内售卖不同价格的水果。公司需要在每个小时都需要购买水果,求买水果最便宜的方案。
思路:就是一个区间修改,单点查询的题。一开始就在想不会让写线段树吧,但是先写了暴力,结果只过了30多,我就开始写线段树了,结果也没写对。
最后在别的帖子里看到初始值设为Integer.MAX_VALUE,暴力就能100%了。题目给的1000,我设的1001,这都能骗人的吗?我真的服了呀,哈哈哈哈哈哈哈

2.修正算数公式

这道题没写,详情可以看这里 ,还有大佬的思路

3.团队能完成的项目最大价值

题目描述:有3个团队,每个团人都有一定的人数。有m个项目,给出每个项目分别需要各个团队多少人以及每个项目的价值。求团队能完成的项目最大价值
思路:一下子就想到了背包,但是容量有3个维度,我在想是多重背包吗?本质也就是0-1背包,三下五除二写完了,结果就只过18%。不知道是状态定义错了还是转移方程错了,最后也没改出来。
下面给我的错误代码,求大佬交流

// s1,s2,s3分别表示3个团队的人力数
int[][][] dp = new int[s1+1][s2+1][s3+1]
// 项目价值
int[] val = new int[m];
// 项目需要人力数
int[][] need = new int[m][3];

for(int i=1;i<=m;++i){
    for(int j=s1;j>=need[i-1][0];--j){
        for(int k=s2;k>=need[i-1][1];--k){
            for(int x=s3;x>=need[i-1][2];--x){
                dp[j][k][x] = Math.max(dp[j][k][x],dp[s1-j][s2-k][s3-x] + val[i-1]);
            }
        }
    }
}
return dp[s1][s2][s3];
#华为机试##笔试题目##笔试题型##华为#
全部评论
刚考完机试,想问一下 第二题写到一半没提交就到时间自动交卷了,第一题测试通过但没提交,主要是担心提交之后就都提交了,这样的情况那代码会保存提交吗?求助
1 回复 分享
发布于 2022-04-28 15:04
请问大概啥时候出成绩啊
点赞 回复 分享
发布于 2022-04-28 10:05
感觉应该是:`dp[j][k][x] = max(dp[j-need[i][0]][k-need[i][1]][x-need[i][2]]+value[i],dp[j][k][x]);`
点赞 回复 分享
发布于 2022-04-28 11:08
直接写背包会超内存,得提取背包容量和重量的后面多少个0开辟小一点的背包数组才能过
点赞 回复 分享
发布于 2022-04-28 13:23
第三道题,感觉挺简单的,没用dp,直接用线性规划,这里因为每个系数只能是0或者1,因此可以用一个数的每一位来表示每个系数,例如11110000。从1-(1<<n)直接的每个数枚举一遍就可以了
点赞 回复 分享
发布于 2022-04-28 20:29
你的OD机考题看着不简单呀🤣,我同事去年考试说他抽到的都很简单,你是研发岗位么?
点赞 回复 分享
发布于 2022-04-29 17:44
第三题我使用暴力递归回溯;测试都通过了
点赞 回复 分享
发布于 2022-05-15 16:57

相关推荐

6 34 评论
分享
牛客网
牛客企业服务