滴滴 研发 笔试第一题只能ac 27%,求交流

破案了,楼下老哥举出了反例,的确是代码有问题,不能解决诸如3 2 1 4这类输入。

# -*- coding=utf-8 -*-
class Solution():
    """魔法杖最高能量
    """
    def maxMagicStickPower(self, n, m, powers):
        """魔法仗能量由最小的能量值的魔法石决定,那么每次找最小和最小邻居中最小融合
        Args:
            n (int): 魔法石个数
            m (int): 可以融合魔法石的次数
            powers (list): 魔法石能量数组
        """
        if m == 0:
            return min(powers)
        for i in range(m):
            if len(powers) == 1:
                return powers[0]
            minPowerIndex = powers.index(min(powers))
            if minPowerIndex == 0:
                powers[minPowerIndex:minPowerIndex+2] = [powers[minPowerIndex]
                                                         + powers[minPowerIndex+1]]
            elif minPowerIndex == len(powers)-1:
                powers[minPowerIndex-1:minPowerIndex+1] = [powers[minPowerIndex-1]
                                                           + powers[minPowerIndex]]
            else:
                if powers[minPowerIndex+1] > powers[minPowerIndex-1]:
                    powers[minPowerIndex-1:minPowerIndex+1] = [powers[minPowerIndex-1]
                                                               + powers[minPowerIndex]]
                else:
                    powers[minPowerIndex:minPowerIndex+2] = [powers[minPowerIndex]
                                                             + powers[minPowerIndex+1]]
        return min(powers)
def main():
    n, m = map(int, input().split())
    powers = list(map(int, input().split()))
    ex = Solution()
    print(ex.maxMagicStickPower(n, m, powers))
if __name__ == "__main__":
    main()
#网易##滴滴#
全部评论
这道题该怎么解决呢
点赞 回复 分享
发布于 2018-10-10 21:02
同27
点赞 回复 分享
发布于 2018-10-10 21:04
同样的思路过9%不晓得测试用例是什么。第二题倒是简单,栈的所有出栈顺序。
点赞 回复 分享
发布于 2018-10-10 21:05
同27,自己测的数据都过了
点赞 回复 分享
发布于 2018-10-10 21:12
如果最小值有多个,你要选择哪一个?
点赞 回复 分享
发布于 2018-10-10 21:19
不太懂python,你这个是不是把所有参与调整的位置全变成求和? 如果是就有问题,比如下面这个数组调整两次 1 1 5 9 应该是 2 5 9->7 9,结果是7 你这个方法就是2 2 5 9-> 4 4 5 9 ,return 4
点赞 回复 分享
发布于 2018-10-10 21:21
有问题 3 2 1 4 如果贪心的话就会变成 334 64 最后输出4 但是应该是55 最后输出5
点赞 回复 分享
发布于 2018-10-10 21:32
首先找到可能最大的数字      r = sum/(n-m) 找到最小的数字(第m-1为最小可能的数字 找这个数有点麻烦  我就用最小的代替了)   l = min; 然后while(l<=r){     mid  = (l+r)/2     对mid进行试探   划分区间  所有区间大于等于mid   且区间数大于等于m-n 说明这个数小了     反之 } A了91 思路不知道是不是错了  其实后来想想 要保证所有区间和大于等于mid   一定要有一个区间等于mid 且区间数要等于m-n才是。。。
点赞 回复 分享
发布于 2018-10-10 21:38
public class main2 {     public static boolean func(long mid, int[] v, int n, int m) {         int ans = 0, i, tmp = 0;         for (i = 0; i < n; i++) {             if ((tmp + v[i]) >= mid) {                 ans++;                 tmp = v[i];             } else                 tmp += v[i];         }         if (ans == 0)             ans = 1;         if (ans >= (n - m))             return true;         else             return false;     }     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         long sum = 0, l = Long.MAX_VALUE, r, mid;         int n, m;         n = in.nextInt();         m = in.nextInt();         int[] v = new int[n];         for (int i = 0; i < n; i++) {             v[i] = in.nextInt();             sum += v[i];             l = Math.min(l, v[i]);         }         r = sum / (n - m);         while (l <= r) {             mid = (l + r) / 2;             if (func(mid, v, n, m))                 l = mid + 1;             else                 r = mid - 1;         }         System.out.println(r);     } } 贴个代码  嘴巴说不清楚怕  有好的思路记得@一下我
点赞 回复 分享
发布于 2018-10-10 21:41

相关推荐

拒绝无效加班的小师弟很中意你:求职意向没有,年龄、课程冗余信息可以删掉,需要提升项目经历。排版需要修改。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务