H****S 发帖数: 1359 | 1 有一个Array。一次操作定义为对于其中每一个元素加一或者减一 (每个元素既可以加
一也可以减一,不必都一样),问至少需要多少此这样的操作,可以让Array里面的数
都相等。如果不可能达到,输出-1. |
r********7 发帖数: 32 | 2 从这个操作上可以看出,array中的两个数之间的差每次只会变化+2或者-2,而最终可
以两个数之间的差要变为0,所以如果通过这种操作能使array里面的数都相等,array
里面的数要么都是偶数要么都是奇数。
假设array里面的元素都是整数。
先考虑最简单的情况:
(1)array只有两个数,那么很容易验证:让array里面的元素都相等的操作次数应该
是(y-x)/2。
(2)array有两个以上的数,这个时候可以利用(1)中的结论,因为要使所有的元素
相等等价于使元素之间两两相等。比如现在有a[0] = x,a[1] = y,a[2] = z三个元素并
假设x
第一步:先让a[0]和a[1]相等,这个过程中a[2]进行与a[1]一样的操作,需要(y-x)/2
次操作,得到
a[0] = a[1] = (x+y)/2, a[2] = z-(y-x)/2
第二步:让a[0],a[1]与a[2]相等,需要(z-y)/2次操作,
最终得到
a[0] = a[1] = a[2] = (z+x)/2
两步一共需要(z-x)/2次操作。对于有3个以上元素的情况可以类推。
同时,这已经是最小的次数了,因为即使要让a[0]和a[2]相等,也需要(z-x)/2次。
所以最小次数应该是(最大值-最小值)/2。 |
H****S 发帖数: 1359 | 3 Bingo! This is a prefect answer:-) So in the process of transformation,
whenever we detected abs(a[i] - a[i + 1]) == 1, the program should
immediately output -1.
array
【在 r********7 的大作中提到】 : 从这个操作上可以看出,array中的两个数之间的差每次只会变化+2或者-2,而最终可 : 以两个数之间的差要变为0,所以如果通过这种操作能使array里面的数都相等,array : 里面的数要么都是偶数要么都是奇数。 : 假设array里面的元素都是整数。 : 先考虑最简单的情况: : (1)array只有两个数,那么很容易验证:让array里面的元素都相等的操作次数应该 : 是(y-x)/2。 : (2)array有两个以上的数,这个时候可以利用(1)中的结论,因为要使所有的元素 : 相等等价于使元素之间两两相等。比如现在有a[0] = x,a[1] = y,a[2] = z三个元素并 : 假设x
|
l*x 发帖数: 14021 | 4 Should be (a[i]+a[i+1])#2 '=0 which means the sum of these two number is odd
. This way, you can output -1 earlier.
【在 H****S 的大作中提到】 : Bingo! This is a prefect answer:-) So in the process of transformation, : whenever we detected abs(a[i] - a[i + 1]) == 1, the program should : immediately output -1. : : array
|
z****i 发帖数: 102 | 5 The final equal number needs to be equal to the average of all numbers.
Otherwise it is not minimum. The number of changes is the sum of abs(num-ave
). |