题意
请参考LRJ白第一章例题3
思路
大概是个构造题。
解决的方法是把整个题转化成一个方程组，令每个人手里的初始金币数量为Ai(已知)，送出数量Xi,受付数量Yi,最终每个人金币数量M(已知)，这样得到由若干形如Ai-Xi+Yi=M方程组成的方程组，当所有方程形式一样时，考虑逐个联立消去未知量，最终得到了关于X1和Xi的若干等式（注意到Xi和Yi+1的相等关系），我们的目标是令Xi之和最小，我们把所有Xi加在一起，就得到了一个仅关于X1的和式。
这个和式的形式可以几何表示是求数轴上一个点，使得其与若干已知点距离之和最短，这个问题的解取在中位数，这样本问题就可以解决了。（中位数是解的想法在白书上有详细的证明，使用反证法）
综合来看，本体需要适当转化，数学变形，数形结合。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; long long n; long long c[1000005]; int main() { while(scanf(" %lld",&n) != EOF) { unsigned long long m = 0; for(int i = 1; i <= n; i++) { scanf(" %llu",&c[i]); m += c[i]; } m /= n; for(int i = 1; i <= n; i++) { c[i] -= m; c[i] += c[i-1]; } sort(c,c+n); long long rf; if(n % 2) { rf = c[n/2]; } else { rf = (c[n/2] + c[n/2-1])/2; } long long res = 0; for(int i = 0; i <= n-1; i++) { res += abs(c[i] - rf); } printf("%lld\n",res); } return 0; } |
