loj10010糖果传递
题目描述
原题来自：HAOI 2008
有 n 个小朋友坐成一圈，每人有 a_i 颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 1 。求使所有人获得均等糖果的最小代价。
输入格式
第一行有一个整数 n ，表示小朋友个数；
在接下来 n 行中，每行一个整数 a_i。
输出格式
输出使所有人获得均等糖果的最小代价。
样例
样例输入
4
1
2
5
4
样例输出
4
数据范围与提示
对于 30% 的数据，n<=1000；
对于 100% 的数据，n<=1e6，保证答案可以用 64 位有符号整数存储。
__________________________________________
很经典的题目，最初是在蓝书上看到的。
n个孩子围坐在一起，每个孩子手中有糖，通过传递让糖果平均。
每个孩子有a_i个糖果，传给下一个孩子b_i个糖果，使他们平均。当然可能是下一个孩子传给他，那么b_i为负数。
这样就是求sum(abs(b_i))
平均值ave是可以求出来的，那么
a_1+b_n-b_1=ave
a_2+b_1-b_2=ave
a_3+b_2-b_3=ave
...
a_n+b_n-1+b_n=ave
变形的
b_1=a_1+b_n-ave
b_2=a_2+b_1-ave
b_3=a_3+b_2-ave
......
b_n=a_n+b_n-1-ave
其中a_i和ave已知，设a_i-ave为c_i，上面的式子变为：
b_2=b_1-c_2
b_3=b_2-c_3=b_1-c_2-c_3
...
b_n=b_1-c_2-c_3-c_4-...-c_n
b_1=b_1-c_2-c_3-c_4-...-c_n-c_1
我们要求的是等号左侧的所有b的绝对值的最小值，也就是求等号右侧所有式子的绝对值和的最小值，而右侧只有b1是未知量。那么式子就变成了
|x-d|
x是未知量，而d是已知量。
那么就成了数轴上x点到d点的距离。
而d有好多个，求得是x。所以就变成了，求数轴上某一点数轴上n个已知点的距离之和最小。
这就用到了中位数。也就是把所有已知点排序，中间点的位置就是x点。
（奇数个已知点就是中间的，偶数个已知点，中间两个点间的所有的都符合要求）
__________________________________________
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e6+10;
4 long long sz[maxn],ssz[maxn];
5 long long n,ave;
6 inline long long jdz(long long x,long long y)
7 {
8 return x>y?x-y:y-x;
9 }
10 int main()
11 {
12 scanf("%lld",&n);
13 for(int i=1;i<=n;++i)
14 {
15 scanf("%lld",&sz[i]);
16 ave+=sz[i];
17 }
18 ave/=n;
19 for(int i=1;i<=n;++i)
20 {
21 sz[i]-=ave;
22 ssz[i]=sz[i]+ssz[i-1];
23 }
24 sort(ssz+1,ssz+n+1);
25 long long b=ssz[(1+n)>>1];
26 long long ans=0;
27 for(int i=1;i<=n;++i)
28 ans+=jdz(b,ssz[i]);
29 cout<<ans;
30 return 0;
31 }
最新文章
- 和 Thrift 的一场美丽邂逅
- 226 Invert Binary Tree
- More on Conditions - To Compare -Comparing Sequences and Other Types
- C语言redirection
- [ZOJ 3662] Math Magic (动态规划+状态压缩)
- Educational Codeforces Round 7 C. Not Equal on a Segment 并查集
- DTCMS自定义标签：面包屑导航，栏目中通过栏目调用名称获得栏目名称
- freemarker入门教程
- cocoa pods 安装 转载
- spring框架详解
- pro-engineer&UG
- The mkdir Command
- Salesforce中的单点登录简介
- COBOL和C#比较
- Linix下修改mysql服务器编码
- scp ssh： connect to host 9.123.159.41 port 22：connection refused的解决办法
- JVM——字节码增强技术简介
- Loadrunner对https协议（单双向SSL）的web端性能测试
- OpenGL学习--07--模型加载(obj)
- startActivities的使用