首页 > 代码库 > UVa11300 - Spreading the Wealth
UVa11300 - Spreading the Wealth
题意
n个人围成一圈，每个人都有一定数量的金币，金币总数可被n整除，现可将手中金币给左右相邻的人，最终使每人手中的金币数相等，求最少转移的金币数量。
思路
设a[i]给了a[i-1]x1个金币，从a[i+1]拿到x2个金币，则有
a1-x1+x2 = m (此时x1为给an的金币数) 另 c1 = a1 - m 则 x2 = x1 -c1
a2-x2+x3 = m ,则c2 = c1+a1-m x3 = x1 - c2
...
|x1| + |x1-C1|+...+|x1-Cn-1|,要求这个最小，那么就是要x1为这些数的中位数
总结
学会数学分析的方法，总结规律并转换成代码
#include <iostream>#include <cstdio>#include <algorithm>typedef long long LL;const int maxn = 1e6 + 5;LL a[maxn],c[maxn],tot,m; //数组a为每个人金币的数量 m为最后相等时的金币数using namespace std;int main(){ int n; while(scanf("%d",&n) == 1) { tot = 0; for(int i = 1; i <= n; i++) { cin >> a[i]; tot += a[i]; } m = tot / n; c[0] = 0; for(int i = 1; i < n; i++) { c[i] = c[i-1] + a[i] - m; } sort(c,c+n); LL x1 = c[n/2],ans = 0; for(int i = 0; i < n; i++) { ans += abs(x1 - c[i]); } cout << ans <<endl; } return 0;}
UVa11300 - Spreading the Wealth
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。