算法——找规律

张开发
2026/4/17 8:50:32 15 分钟阅读

分享文章

算法——找规律
本质这类题型的本质就是发现规律从而找到更简单的算法例题暴力解法那就是从前往后或者从后往前枚举所有可能的情况算法复杂度较高。首先要结合正难则反的思路然后把s-t的最小操作次数转换成t-s的最小操作次数当然*2和-1要换成/2和1我们可以分情况讨论t的上一个数变成t有如下几种情况可以发现如果t是奇数t的上一个数就是t1如果t是偶数的话t的上一个数可以是t1也可以是t/2不过加x个1再除以2等价于个除以2再加y个1而yx因此偶数的第三种情况的操作次数一定大于前两种情况所以如果t是偶数的话就除以2。不过后来发现以上假设都是基于t s的情况如果t s 有些推论就不成立比如偶数中的第三种类型最前面不一定有*2。故此我们补充完整的情况少量的箭引爆气球就是尽量在重叠区射箭一次性引爆多个气球。对于没有和其他气球重叠起来的气球需要单独的箭来引爆。这里有一个问题就是假设一个气球分别和两个气球重叠应该向那个区域射箭其实无论向哪儿射箭最后没被射的气球都成了单独的气球仍旧需要箭射爆。所以只要是重叠区以及单独的气球都需要射箭。我们要找的就是重叠区和单独气球的数量。

更多文章