最小代价均匀分配糖果

"糖果传递.md" 这道题目是一道典型的算法问题，属于IT技术中的算法题解范畴。问题的核心是解决如何在一组围绕一圈的小朋友中，通过最小代价地传递糖果，使得每个小朋友手中的糖果数量均等。这个问题可以看作是一种分配问题，同时也涉及到图论中的环形结构。 首先，我们需要理解题目的输入和输出格式。输入包括一个正整数n，表示小朋友的数量，以及n行整数a[i]，表示每个小朋友初始拥有的糖果数量。输出是实现均等分配所需的最小代价。 数据范围是1≤n≤1000000，表明问题规模可大可小，而且每个小朋友的糖果数量0≤a[i]≤2×10^9，意味着糖果数量可能非常大。重要的是，题目保证了总能找到一种解决方案，即能够通过传递糖果使所有小朋友的糖果数量相等。 参考答案给出的C++代码中，首先读入小朋友的数量n和他们的糖果数，然后计算总糖果数sum和平均糖果数ave。接下来，定义数组c来存储从第一个小朋友开始，每个位置上小朋友应该有的糖果数（基于平均值）。接着对数组c进行排序，找到中间位置的值mid，这个值将作为目标糖果数，每个小朋友应该拥有mid个糖果。 然后，通过遍历数组c并计算每个小朋友的糖果数与mid的差值的绝对值，累加这些差值得到的就是最小代价。最后输出这个累加的结果，即为答案。 这个问题的解决方案利用了二分的思想，找到中间值作为目标，因为在一个环形结构中，平均值并不一定是最佳解，而中间值更有可能让转移糖果的代价最小。代码中的`sort(c+1, c+n+1)`用于对c数组进行升序排序，`ans+=abs(c[i]-mid)`计算每个小朋友与目标值的差，并累加到总代价中。 这个算法的时间复杂度主要取决于排序操作，大约为O(n log n)，空间复杂度为O(n)，适用于题目给定的数据范围。通过这样的方法，我们可以有效地解决大规模数据下的糖果传递问题，找出最小代价的方案。