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
). |
