Open Wizmann opened 3 years ago
Problem
给定一个正整数数组A。规定以下两种操作：
每一个操作可以执行任意次。问在若干次操作之后，max(A[]) - min(A[])的最小值。
max(A[]) - min(A[])
首先研究对A[i]的两种操作。
如果A[i]是偶数，那么它只能除2，直到结果为奇数为止。如果A[i]是奇数，它只能进行一次乘2操作，因为乘2之后A[i]就变成偶数了。
所以对于所有的数，其变化范围有：
因此数组变化后的上下界是确定的。 假设已经确定了变化后数组的最小值x。所以对于A[i] < x，则必须进行扩大操作，使其等于大于等于x的最小值。这样一来，我们确定了下界，同时使上界尽可能小，保证了解是最优的。
实现方法如下：
首先把A[i]化为其最小值，每次取出最小值做为下界，最大值做为上界，求当前上下界的差。 然后：
Code
Description
Problem
给定一个正整数数组A。规定以下两种操作：
每一个操作可以执行任意次。问在若干次操作之后，
max(A[]) - min(A[])的最小值。Solution
首先研究对A[i]的两种操作。
如果A[i]是偶数，那么它只能除2，直到结果为奇数为止。如果A[i]是奇数，它只能进行一次乘2操作，因为乘2之后A[i]就变成偶数了。
所以对于所有的数，其变化范围有：
因此数组变化后的上下界是确定的。 假设已经确定了变化后数组的最小值x。所以对于A[i] < x，则必须进行扩大操作，使其等于大于等于x的最小值。这样一来，我们确定了下界，同时使上界尽可能小，保证了解是最优的。
实现方法如下：
首先把A[i]化为其最小值，每次取出最小值做为下界，最大值做为上界，求当前上下界的差。 然后：
Code