1. 首页
  2. 题解列表
  3. 2277题题解

蓝桥杯2018年第九届真题-倍数问题 搜索（限制搜索范围）

815 阅读 3 评论
原题链接：蓝桥杯2018年第九届真题-倍数问题

解题思路:

注意事项:

参考代码:

n, k = map(int, input().split())

nums = [int(i) for i in input().split()]
nums.sort(reverse=True)
ans = 0
i = 0
limit = n - 1

while i < limit - 2:
    l = i + 1
    r = i + 2
    while l < limit :
        while r < limit :
            if (nums[i] + nums[l] + nums[r]) % k == 0:
                ans = max(ans, nums[i] + nums[l] + nums[r])
                limit = r
                l += 1
                r = l + 1
            else:
                r += 1
        l += 1
        r = l + 1
    i += 1
    # limit = n - 1 删掉这一行就能过，但我也不知道为什么，不删就只能到82

                
print(ans)


点赞(0)
　

0.0分

2 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 3 条评论

Hello 2年前 回复TA 
@Hello 因为列表nums[]里的数字是从大到小排列的，当找到一组i,l,r满足(nums[i] + nums[l] + nums[r]) % k == 0时，因为题目要求的是这三个数之和最大，之后满足(nums[i] + nums[l] + nums[r]) % k == 0的一组i,l，r必不可能大于等于上一组的r，否则一定不会比上一组的(nums[i] + nums[l] + nums[r])大。
菜菜ccEL 2年前 回复TA 
@Hello 为什么要limit=r啊？
Hello 2年前 回复TA 
要求三个数和的最大，先将列表中的数据按照从大到小的顺序排序，limit = r是这个算法的精髓，限制了进一步搜索可行解的范围。