1 solutions
-
0
对于每个人和平均值ave相比,要么少要么多,此时引用一个x[i]表示i人和i - 1之间的交易,正负可表示传递方向,得出公式: a[i] + x[i] + x[i + 1] = ave (其中x[i]有正有负)后面将设定大于0,表示当前i人向左传递数量
A1-X1+X2=ave -> X2=ave-A1+X1 = X1-C1 (假设C1=A1-ave)这里引入一个c A2-X2+X3=ave -> X3=ave-A2+X2=2ave-A1-A2+X1=X1-C2 (即C2=A1+A2-2ave=A2+C1-ave) 我们希望Xi的绝对值之和尽量小,即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小 所以找一个x1满足这个条件。
ac code:
#include<bits/stdc++.h> typedef long long LL; using namespace std; const int N = 1e6 + 10; int n; LL a[N],su,ave,ans; LL c[N]; int main () { cin >> n; for(int i = 1;i <= n;++ i) { cin >> a[i]; su += a[i]; } ave = su / n; for(int i = 1;i <= n;++ i) { c[i] = c[i - 1] + ave - a[i - 1]; } sort(c + 1,c + 1 + n); LL m = c[(n + 1) / 2]; for(int i = 1;i <= n;++ i) { ans += abs(m - c[i]); } cout << ans; return 0; }
- 1
Information
- ID
- 7002
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 30
- Accepted
- 3
- Uploaded By