AcWing 122. 糖果传递
原题链接
中等
作者:
小明同学hh
,
2020-11-30 17:14:03
,
所有人可见
,
阅读 406
/*** x2 x3
* a1 a2 a3
* x1 x4
* a8 a4
* x8 x5
* a7 a6 a5
* x7 x6
*
*
* a1 - x1 + x2 = a
* a2 - x2 + x3 = a
* a3 - x3 + x4 = a
* a4 - x4 + x5 = a
* a5 - x5 + x6 = a
* a6 - x6 + x7 = a
* a7 - x7 + x8 = a
* a8 - x8 + x1 = a
*
* x1 = x1
* x8 = x1 - (a - a8) = x1 + (a8 - a)
* x7 = x1 - (2a - (a8 + a7)) = x1 + (a8 - a) + (a7 - a)
* x6 = x1 - (3a - (a8 + a7 + a6)) = x1 + (a8 - a) + (a7 - a) + (a6 - a)
* x5 = x1 - (4a - (a8 + a7 + a6 + a5))
* x4 = x1 - (5a - (a8 + a7 + a6 + a5 + a4))
* x3 = x1 - (6a - (a8 + a7 + a6 + a5 + a4 + a3))
* x2 = x1 - (7a - (a8 + a7 + a6 + a5 + a4 + a3 + a2))
* x1 = x1 - (8a - (a8 + a7 + a6 + a5 + a4 + a3 + a2 + a1))
* 注意 :最后一行就是 x1 = x1
*
*
* min {|x1| + |x2| + |x3| + |x4| + |x5| + |x6| + |x7| + |x8|}
* a = (a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8) / 9
*/
// 2325ms
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
LL a[N];
int main() {
scanf("%d", &n);
LL sum = 0;
for (int i = 1; i <= n; i ++ ) {
scanf("%lld", &a[i]);
sum += a[i];
}
sum /= n;
for (int i = n; i >= 1; i -- ) {
a[i] = a[i] - sum + a[i + 1];
}
a[1] = 0;
sort(a + 1, a + 1 + n);
LL res = 0;
for (int i = 1; i <= n; i ++ ) res += abs(a[i] - a[(n + 1) / 2]);
printf("%lld\n", res);
return 0;
}
// 776ms
// 受到小呆呆大佬的启发 不需要排序 直接找中位数就可以
// 时间复杂度大大优化
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
LL a[N];
int n;
LL find_k(int l, int r, int k) {
if (l >= r) return a[l];
int i = l - 1, j = r + 1;
LL x = a[l + r >> 1];
while ( i < j ) {
while (a[++ i] < x);
while (a[-- j] > x);
if (i < j) swap(a[i], a[j]);
}
int sl = j - l + 1;
if (sl >= k) return find_k(l, j, k);
else return find_k(j + 1, r, k - sl);
}
int main() {
scanf("%d", &n);
LL sum = 0;
for (int i = 1; i <= n; i ++ ) {
scanf("%lld", &a[i]);
sum += a[i];
}
sum /= n;
for (int i = n; i >= 1; i -- ) {
a[i] = a[i] - sum + a[i + 1];
}
LL k = find_k(1, n, (n + 1) >> 1);
sum = 0;
for (int i = 1; i <= n; i ++ ) {
sum += abs(a[i] - k);
}
printf("%lld\n", sum);
return 0;
}