给定一个所有元素大于0的无序序列,每次操作会给所有的元素减去a(a > 0), 然后再选择一个元素额外减去b(b > 0)。问最少需要多少次操作可以使所有元素小于等于0。
时间: 2024-06-02 16:11:51 浏览: 47
最小操作次数使数组元素相等(找规律)1
首先我们可以考虑每次选择哪个元素额外减去b,因为每个元素都是等价的,所以我们可以选择最大的元素进行额外减去b,这样可以最大限度地减少操作次数。
假设序列中最大的元素为max,那么需要进行的操作次数为(max-1)/a+1,其中(max-1)表示将max减到1所需要的操作次数,而+1则表示将max减到0所需要的额外一次操作。
那么我们只需要将每个元素都减到0即可,所需要的总操作次数为所有元素减到0所需的最小操作次数,即max((ai-1)/a+1),其中ai表示第i个元素的初始值。
时间复杂度为O(n),可以通过本题。
阅读全文